← 返回题目列表

AtCoder · abc375_g

G. 道路受阻 2

中文机器翻译题面 查看原题

分数: 575 点

问题陈述

在AtCoder的国家里,有 N 城市编号 1 to N,和 M 道路编号 1 to M.
路 i 连接城市 A_i 和 B_i 双向且长度为 C_i.

对于每个 i = 1, \ldots, M,判断以下两个值是否不同。

  • 距城市最短距离 1 前往城市 N 当所有道路均可通行时
  • 距城市最短距离 1 前往城市 N 当 M - 1 道路以外的道路 i 还过得去

如果城市 从市区可到达 N 从城市可以到达 1 在其中一种情况下,而不是另一种情况下,这两个值被视为不同。

约束

  • 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
  • 城市 N 从城市可以到达 1 当所有道路均可通行时。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

输出

打印 M 行。的 i- 第行应包含 Yes 如果距城市的最短距离 1 前往城市 N 当所有道路均可通行时与当 M - 1 道路以外的道路 i 还可以,并且 No 否则。

如果城市 从市区可到达 N 从城市可以到达 1 在其中一种情况下,而不是另一种情况下,这两个值被视为不同。


示例输入 1

3 3
1 2 5
1 3 10
2 3 6

示例输出 1

No
Yes
No

当所有道路均可通行时,距城市的最短距离 1 前往城市 3 is 10.

  • 当道路以外的两条道路 1 可以通过,最短距离是 10.
  • 当道路以外的两条道路 2 可以通过,最短距离是 11.
  • 当道路以外的两条道路 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 is 1.

当道路以外的5条道路 6 可以通过,最短距离是 2.


示例输入 3

2 1
1 2 1

示例输出 3

Yes

当道路以外的零路 1 还过得去,城市 从城市无法到达 2 从城市无法到达 1.