Problem
Cho một đồ thị có hướng có các cạnh được gán một số trọng số (độ dài) không âm. Chúng ta cần tìm hai đỉnh, đường đi ngắn nhất giữa hai đỉnh đó có độ dài lớn nhất.
Đầu vào
Dòng đầu tiên chứa số đỉnh N ≤50. Tiếp theo là ma trận kề của đồ thị, tức là N hàng, mỗi hàng chứa N số. Số thứ j trong hàng thứ i của ma trận kề xác định độ dài của cạnh dẫn từ đỉnh thứ i đến đỉnh thứ j. Độ dài có thể nhận bất kỳ giá trị nào từ 0 đến 1000000. Đảm bảo rằng không có số 0 trên đường chéo chính của ma trận.
Đầu ra
In một số duy nhất – độ dài của đường dẫn mong muốn.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|