最短経路を見つける 3
あなたには、n 個の都市と、それらを結ぶ m 本の双方向道路から成る地図が与えられています。各道路には非負の整数長があり、これは で示されます。あなたの行うべき作業は、都市
1 から都市 n までの最短経路の長さを求めることです。入力
最初の行には、都市の数と道路の数を表す
n と m () が空白区切りで与えられます。続く
m 行のそれぞれには、、、そして () といった 3 つの整数が空白区切りで与えられます。これは都市 と都市 を結ぶ道路があり、その長さが であることを意味します。出力
都市
1 から都市 n までの最短経路の長さを表す整数を 1 つ出力してください。例
入力 | 出力 |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB