← 返回题目列表

Codeforces · 567/E

E. 总统和道路

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

Berland有n个城市,首都位于城市s,总统的历史故乡位于城市t(s≠t)。城市之间通过单向道路连接,每条道路的行驶时间均为正整数。

总统每年都会访问一次他的历史故乡 t,为此,他的车队会经过从 s 到 t 的一些路径(他总是乘坐私人飞机返回)。由于总统是一个非常忙碌的人,他总是选择从 s 到 t 的路径,沿着这条路径他会走得最快。

公路和铁道部希望了解每一条道路:总统出访期间是否一定会经过它,如果没有,是否有可能对其进行修复,使其一定会被纳入从首都到总统历史故乡的最短路径中。显然,这条路无法修好,所以路上的行驶时间不到一小时。 Berland 部门与其他部门一样,对维持预算感兴趣,因此想知道修复道路的最低成本。此外,它非常注重准确性,因此它会修复道路,使道路上的行驶时间始终为正整数。

输入

第一行包含四个整数 n、m、s 和 t (2 ≤ n ≤ 105; 1 ≤ m ≤ 105; 1 ≤ s, t ≤ n) — Berland 的城市和道路数量、首都和总统家乡的数量 (s ≠ t)。

接下来的 m 行包含道路。每条道路均以三个整数 ai、bi、li 的形式给出(1 ≤ ai,bi ≤ n;ai ≠ bi;1 ≤ li ≤ 106)——第 i 条道路连接的城市以及沿该道路骑行所需的时间。道路是从ai市直达bi市的。

城市编号为 1 到 n。每对城市之间可以有多条道路。保证沿路有一条从 s 到 t 的路径。

输出

打印 m 行。第 i 行应包含有关第 i 条道路的信息(道路按照输入中出现的顺序进行编号)。

如果总统在旅行期间肯定会沿着这条路骑行,则该行必须包含一个单词“YES”(不带引号)。

否则,如果第i条路可以修复,使其行驶时间保持为正,那么总统肯定会沿着它骑行,打印空格分隔的单词“CAN”(不带引号),以及修复的最低成本。

如果我们不能让总统一定会沿着它骑行,请打印“NO”(不带引号)。

示例

输入 #1

6 7 1 6
1 2 2
1 3 10
2 3 7
2 4 8
3 5 3
4 5 2
5 6 1

输出 #1

YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES

输入 #2

3 3 1 3
1 2 10
2 3 10
1 3 100

输出 #2

YES
YES
CAN 81

输入 #3

2 2 1 2
1 2 1
1 2 2

输出 #3

YES
NO

注意

修路成本是修路前后骑行时间的差值。

在第一个样本中,总统最初可以选择以下两种方式之一乘坐:1 → 2 → 4 → 5 → 6 或 1 → 2 → 3 → 5 → 6。