Road Blocked 2

题目描述

在 AtCoder 王国，有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$。
道路 $i$ 双向连接城市 $A_i$ 和 $B_i$，长度为 $C_i$。 对于每个 $i = 1, \ldots, M$，判定以下两个数值是否不同。

当所有道路都可通行时，从城市 $1$ 到城市 $N$ 的最短距离 当除道路 $i$ 之外的 $M - 1$ 条道路可通行时，从城市 $1$ 到城市 $N$ 的最短距离

如果在这两种情况下，城市 $N$ 能从城市 $1$ 到达的状况在两种情况中之一能达通而另一种不能达通，则认为这两个数值不同。

输入格式

输入按下述格式由标准输入提供： $N$ $M$ $A_1$ $B_1$ $C_1$ $\vdots$ $A_M$ $B_M$ $C_M$

输出格式

打印 $M$ 行。第 $i$ 行应当包含 $Yes$，如果当所有道路都可通行时从城市 $1$ 到城市 $N$ 的最短距离与除道路 $i$ 之外的 $M - 1$ 条道路可通行时的最短距离不同；否则输出 $No$。 如果在这两种情况下，城市 $N$ 能从城市 $1$ 到达的状况在两种情况中之一能达通而另一种不能达通，则认为这两个数值不同。

3 3
1 2 5
1 3 10
2 3 6

No
Yes
No

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

No
No
No
No
No
Yes

2 1
1 2 1

Yes

提示

$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$ 到达。 所有输入值均为整数。当所有道路都可通行时，从城市 $1$ 到城市 $3$ 的最短距离是 $10$。

当除道路 $1$ 之外的两条道路可通行时，最短距离是 $10$。 当除道路 $2$ 之外的两条道路可通行时，最短距离是 $11$。 当除道路 $3$ 之外的两条道路可通行时，最短距离是 $10$。
当所有道路都可通行时，从城市 $1$ 到城市 $4$ 的最短距离是 $1$。 当除道路 $6$ 之外的五条道路可通行时，最短距离是 $2$。
当除道路 $1$ 之外没有道路可通行时，城市 $2$ 无法从城市 $1$ 到达。

标签: AtCoder|abc375G

来源

AtCoder|abc375G