分数: 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.