Problem
Diberi graf terarah yang tepinya diberikan beberapa pemberat bukan negatif (panjang). Kita perlu mencari dua bucu, laluan terpendek antara yang mempunyai panjang terbesar.
Input
Baris pertama mengandungi bilangan bucu N ≤50. Seterusnya datang matriks bersebelahan graf, iaitu, N baris, setiap satunya mengandungi N nombor. Nombor ke-j dalam baris ke-i matriks bersebelahan menentukan panjang tepi menuju dari bucu ke-i ke bucu ke-j. Panjang boleh mengambil sebarang nilai dari 0 hingga 1000000. Ia dijamin bahawa terdapat sifar pada pepenjuru utama matriks.
Output
Cetak satu nombor – panjang laluan yang dikehendaki.
Contoh
| # |
Input |
Output |
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|