Problem
エッジに負でない重み (長さ) が割り当てられた有向グラフが与えられます。 2 つの頂点を見つける必要があります。その間の最短経路が最も長くなります。
入力
最初の行には、頂点の数 N ≤50 が含まれています。次にグラフの隣接行列、つまり各行に N 個の数値が含まれる N 行が来ます。隣接行列の i 行目の j 番目の数値は、i 番目の頂点から j 番目の頂点まで続くエッジの長さを指定します。長さは 0 から 1000000 までの任意の値を取ることができます。行列の主対角にゼロがあることが保証されています。
出力
単一の数値を出力します –目的のパスの長さ。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|