No.49 最短経路問題


時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

$N$頂点$M$辺の重み付き無向グラフが与えられます。

辺$e_i$は頂点$a_i$と頂点$b_i$を結んでいて、$a_i$と$b_i$の間を移動するのに$c_i$のコストがかかります。

頂点$1$から頂点$N$に移動するために必要な最小コストを求めてください。

但し、自己辺($a_i$ = $b_i$となる辺)は与えられず、辺の重複($i \neq j$ のときに$a_i = a_j,b_i = b_j$の両方が成り立つこと)もないことが保証されます。

制約

  • $2 ≦ N ≦ 100000$
  • $1 ≦ M ≦ 200000$
  • $0 ≦ c_i ≦ 100000$

さらに、テストケース1~5では、$2 ≦ N ≦ 100,1 ≦ M ≦ 200 $が

テストケース6~10では、$2 ≦ N ≦ 2000,1 ≦ M ≦ 4000 $が

テストケース11~15では、$c_i = 1$が追加制約として与えられます。

入力形式

入力は以下の形式で標準入力から与えられる。


N M
a_1 b_1 c_1
a_2 b_2 c_2
......
a_M b_M c_M

出力

頂点$1$から頂点$N$に移動するために必要な最小コストを出力してください。

但し、移動できない場合には$-1$を出力してください。

入出力例

入力1

3 2
1 2 3
2 3 5

出力1

8

頂点$1$から頂点$2$に移動するのに$3$のコストがかかり、頂点$2$から頂点$3$に移動するのに$5$のコストがかかります。

入力2

4 1
1 3 33

出力2

-1

残念ながら頂点$1$から頂点$4$に移動することはできません。





解説


解説は公開されていません。