THE BENEFACTOR - Đường đi tổng trọng số lớn nhất.

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Authors:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Cho đồ thị vô hướng liên thông có n đỉnh và n1 cạnh. Hãy tìm một cặp đỉnh u,v sao cho đường đi từ u tới v có tổng trọng số lớn nhất.

Dữ liệu vào:

  • Dòng đầu tiên là số nguyên t cho biết số lượng testcase
  • t nhóm dòng tiếp theo, mỗi nhóm dòng cho biết thông tin về một testcase: Dòng đầu tiên ghi số nguyên dương n cho biết số đỉnh của đồ thị n1 dòng tiếp theo, mỗi dòng ghi ba số nguyên u,v,c cho biết cạnh u,v của đồ thị có trọng số c.

Giới hạn:

  • 1t10
  • 2n50000
  • 0c20000

Kết quả: Gồm t dòng, mỗi dòng ghi kết quả của một testcase tương ứng với thứ tự trong input

Ví dụ:
Input 1:
Copy
1
6
1 2 3
2 3 4
2 6 2
6 4 6
6 5 5
Output 1:
Copy
12

Comments

Please read the guidelines before commenting.


There are no comments at the moment.