AT_abc375_g [ABC375G] 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$ 的最短距离。

注意，如果一种情况下可以从城市 $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

输入 #1

3 3
1 2 5
1 3 10
2 3 6

输出 #1

No
Yes
No

输入输出样例 #2

输入 #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

输入输出样例 #3

输入 #3

2 1
1 2 1

输出 #3

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$
• 当所有道路都可通行时，一定可以从城市 $1$ 到城市 $N$
• 所有输入均为整数

样例解释 1

当所有道路都可通行时，从城市 $1$ 到城市 $3$ 的最短距离为 $10$。

• 当除了第 $1$ 条道路以外的其余 $2$ 条道路可通行时，从城市 $1$ 到城市 $3$ 的最短距离为 $10$。
• 当除了第 $2$ 条道路以外的其余 $2$ 条道路可通行时，从城市 $1$ 到城市 $3$ 的最短距离为 $11$。
• 当除了第 $3$ 条道路以外的其余 $2$ 条道路可通行时，从城市 $1$ 到城市 $3$ 的最短距离为 $10$。

样例解释 2

当所有道路都可通行时，从城市 $1$ 到城市 $4$ 的最短距离为 $1$。
当除了第 $6$ 条道路以外的其余 $5$ 条道路可通行时，从城市 $1$ 到城市 $4$ 的最短距离为 $2$。

样例解释 3

当除了第 $1$ 条道路以外的 $0$ 条道路可通行时，无法从城市 $1$ 到城市 $2$。

由 ChatGPT 4.1 翻译