C - 通行止めの迂回路 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は街 1 から街 N へ移動しようとしています。

N 個の街と M 本の道路があり、i 番目の道路は街 U_i と街 V_i を双方向に結んでいます。

現在、いくつかの道路は工事のため通行止めとなっています。具体的には、S_i = 1 のとき i 番目の道路は通行可能であり、S_i = 0 のとき通行止めで通ることができません。

高橋君は通行可能な道路のみを使って街 1 から街 N へ移動します。移動の際、同じ街や同じ道路を複数回通ってもかまいません。このとき、通る道路の本数（同じ道路を複数回通った場合はその回数分だけ数える）の最小値を求めてください。

ただし、通行可能な道路のみを使ってどのように移動しても街 N にたどり着けない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M < 2 \times 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 同じ組 (U_i, V_i) に対して複数の道路が存在することがある（多重辺がありうる。それぞれの道路について S_i の値は独立に定まる）
  • S_i \in \{0, 1\}
  • 入力はすべて整数である

入力

N M
U_1 V_1 S_1
U_2 V_2 S_2
\vdots
U_M V_M S_M
  • 1 行目には、街の数 N と道路の数 M がスペース区切りで与えられる。
  • 続く M 行にわたって、各道路の情報が与えられる。
  • (i+1) 行目には、i 番目の道路が結ぶ 2 つの街 U_i, V_i と、その道路が通行可能かを表す S_i がスペース区切りで与えられる。

出力

通行可能な道路のみを使って街 1 から街 N へ移動するために通る道路の本数の最小値を 1 行で出力せよ。ただし、移動できない場合は -1 を出力せよ。

入力例 1

4 5
1 2 1
2 4 1
1 3 0
3 4 1
2 3 1

出力例 1

2

入力例 2

5 6
1 2 1
2 3 0
3 5 1
1 4 0
4 5 1
2 4 0

出力例 2

-1

入力例 3

8 12
1 2 1
1 3 0
2 4 1
3 4 1
4 5 0
4 6 1
6 8 1
5 8 1
2 3 1
2 5 1
1 2 0
7 8 1

出力例 3

3

入力例 4

12 20
1 2 1
2 3 1
3 12 0
1 4 1
4 5 1
5 6 1
6 12 1
2 5 0
3 6 1
1 7 0
7 8 1
8 9 1
9 12 1
4 8 1
5 9 0
2 10 1
10 11 1
11 12 1
6 10 0
3 4 1

出力例 4

4

入力例 5

2 1
1 2 1

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is trying to travel from town 1 to town N.

There are N towns and M roads, and the i-th road bidirectionally connects town U_i and town V_i.

Currently, some roads are closed due to construction. Specifically, when S_i = 1, the i-th road is passable, and when S_i = 0, it is closed and cannot be used.

Takahashi travels from town 1 to town N using only passable roads. During the trip, he may pass through the same town or the same road multiple times. Find the minimum number of roads traversed (if the same road is used multiple times, each traversal is counted separately).

However, if it is impossible to reach town N using only passable roads regardless of the route taken, output -1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M < 2 \times 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • There may be multiple roads for the same pair (U_i, V_i) (i.e., multiple edges are possible; the value of S_i is determined independently for each road)
  • S_i \in \{0, 1\}
  • All input values are integers

Input

N M
U_1 V_1 S_1
U_2 V_2 S_2
\vdots
U_M V_M S_M
  • The first line contains the number of towns N and the number of roads M, separated by a space.
  • The following M lines provide information about each road.
  • The (i+1)-th line contains the two towns U_i, V_i connected by the i-th road, and S_i indicating whether the road is passable, separated by spaces.

Output

Output in a single line the minimum number of roads traversed to travel from town 1 to town N using only passable roads. If it is impossible to make the trip, output -1.

Sample Input 1

4 5
1 2 1
2 4 1
1 3 0
3 4 1
2 3 1

Sample Output 1

2

Sample Input 2

5 6
1 2 1
2 3 0
3 5 1
1 4 0
4 5 1
2 4 0

Sample Output 2

-1

Sample Input 3

8 12
1 2 1
1 3 0
2 4 1
3 4 1
4 5 0
4 6 1
6 8 1
5 8 1
2 3 1
2 5 1
1 2 0
7 8 1

Sample Output 3

3

Sample Input 4

12 20
1 2 1
2 3 1
3 12 0
1 4 1
4 5 1
5 6 1
6 12 1
2 5 0
3 6 1
1 7 0
7 8 1
8 9 1
9 12 1
4 8 1
5 9 0
2 10 1
10 11 1
11 12 1
6 10 0
3 4 1

Sample Output 4

4

Sample Input 5

2 1
1 2 1

Sample Output 5

1