G - Road Blocked 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

AtCoder国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 本の道路があります。
道路 i は都市 A_i と都市 B_i を双方向に結び長さは C_i です。

各 i=1,\ldots,M について、以下の 2 つの値が異なるかどうか判定してください。

  • 全ての道路が通行可能なときの、都市 1 から都市 N への最短距離
  • 道路 i 以外の M-1 本の道路が通行可能なときの、都市 1 から都市 N への最短距離

ただし、一方では都市 1 から都市 N に到達可能で、他方では到達不可能なとき、両者の値は異なるとみなします。

制約

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1\leq A_i < B_i \leq N
  • (A_i,B_i) は相異なる
  • 1 \leq C_i \leq 10^9
  • 全ての道路が通行可能なとき、都市 1 から都市 N へは到達可能
  • 入力は全ては整数である

入力

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

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

M 行出力せよ。i 行目には、「全ての道路が通行可能なときの、都市 1 から都市 N への最短距離」と「道路 i 以外の M-1 本の道路が通行可能なときの、都市 1 から都市 N への最短距離」が異なるとき Yes、同じとき No と出力せよ。

ただし、一方では都市 1 から都市 N に到達可能で、他方では到達不可能なとき、両者の値は異なるとみなす。

入力例 1

3 3
1 2 5
1 3 10
2 3 6

出力例 1

No
Yes
No

全ての道路が通行可能なとき、都市 1 から都市 3 への最短距離は 10 です。

  • 道路 1 以外の 2 本の道路が通行可能なときの、都市 1 から都市 3 への最短距離 は 10 です
  • 道路 2 以外の 2 本の道路が通行可能なときの、都市 1 から都市 3 への最短距離 は 11 です
  • 道路 3 以外の 2 本の道路が通行可能なときの、都市 1 から都市 3 への最短距離 は 10 です

入力例 2

4 6
2 3 1
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1

出力例 2

No
No
No
No
No
Yes

全ての道路が通行可能なとき、都市 1 から都市 4 への最短距離は 1 です。

道路 6 以外の 5 本の道路が通行可能なときの、都市 1 から都市 4 への最短距離 は 2 です。

入力例 3

2 1
1 2 1

出力例 3

Yes

道路 1 以外の 0 本の道路が通行可能なとき、都市 1 から都市 2 へは到達できません。

Score : 575 points

Problem Statement

In the nation of AtCoder, there are N cities numbered 1 to N, and M roads numbered 1 to M.
Road i connects cities A_i and B_i bidirectionally and has a length of C_i.

For each i = 1, \ldots, M, determine whether the following two values are different.

  • The shortest distance from city 1 to city N when all roads are passable
  • The shortest distance from city 1 to city N when the M - 1 roads other than road i are passable

If city N can be reached from city 1 in one of these cases but not the other, the two values are considered different.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i < B_i \leq N
  • All pairs (A_i, B_i) are distinct.
  • 1 \leq C_i \leq 10^9
  • City N can be reached from city 1 when all roads are passable.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

Output

Print M lines. The i-th line should contain Yes if the shortest distance from city 1 to city N when all roads are passable is different from the shortest distance when the M - 1 roads other than road i are passable, and No otherwise.

If city N can be reached from city 1 in one of these cases but not the other, the two values are considered different.

Sample Input 1

3 3
1 2 5
1 3 10
2 3 6

Sample Output 1

No
Yes
No

When all roads are passable, the shortest distance from city 1 to city 3 is 10.

  • When the two roads other than road 1 are passable, the shortest distance is 10.
  • When the two roads other than road 2 are passable, the shortest distance is 11.
  • When the two roads other than road 3 are passable, the shortest distance is 10.

Sample Input 2

4 6
2 3 1
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1

Sample Output 2

No
No
No
No
No
Yes

When all roads are passable, the shortest distance from city 1 to city 4 is 1.

When the five roads other than road 6 are passable, the shortest distance is 2.

Sample Input 3

2 1
1 2 1

Sample Output 3

Yes

When the zero roads other than road 1 are passable, city 2 cannot be reached from city 1.