专栏首页饶文津的专栏【CodeForces 567E】President and Roads(最短路)

【CodeForces 567E】President and Roads(最短路)

Description

Berland has n cities, the capital is located in city s, and the historic home town of the President is in city t (s ≠ t). The cities are connected by one-way roads, the travel time for each of the road is a positive integer.

Once a year the President visited his historic home town t, for which his motorcade passes along some path from s to t (he always returns on a personal plane). Since the president is a very busy man, he always chooses the path from s to t, along which he will travel the fastest.

The ministry of Roads and Railways wants to learn for each of the road: whether the President will definitely pass through it during his travels, and if not, whether it is possible to repair it so that it would definitely be included in the shortest path from the capital to the historic home town of the President. Obviously, the road can not be repaired so that the travel time on it was less than one. The ministry of Berland, like any other, is interested in maintaining the budget, so it wants to know the minimum cost of repairing the road. Also, it is very fond of accuracy, so it repairs the roads so that the travel time on them is always a positive integer.

Input

The first lines contain four integers nms and t (2 ≤ n ≤ 105; 1 ≤ m ≤ 105; 1 ≤ s, t ≤ n) — the number of cities and roads in Berland, the numbers of the capital and of the Presidents' home town (s ≠ t).

Next m lines contain the roads. Each road is given as a group of three integers ai, bi, li (1 ≤ ai, bi ≤ nai ≠ bi; 1 ≤ li ≤ 106) — the cities that are connected by the i-th road and the time needed to ride along it. The road is directed from city ai to city bi.

The cities are numbered from 1 to n. Each pair of cities can have multiple roads between them. It is guaranteed that there is a path from sto t along the roads.

Output

Print m lines. The i-th line should contain information about the i-th road (the roads are numbered in the order of appearance in the input).

If the president will definitely ride along it during his travels, the line must contain a single word "YES" (without the quotes).

Otherwise, if the i-th road can be repaired so that the travel time on it remains positive and then president will definitely ride along it, print space-separated word "CAN" (without the quotes), and the minimum cost of repairing.

If we can't make the road be such that president will definitely ride along it, print "NO" (without the quotes).

Examples

input

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

output

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

input

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

output

YES
YES
CAN 81

input

2 2 1 2
1 2 1
1 2 2

output

YES
NO

Note

The cost of repairing the road is the difference between the time needed to ride along it before and after the repairing.

In the first sample president initially may choose one of the two following ways for a ride:1 → 2 → 4 → 5 → 6 or 1 → 2 → 3 → 5 → 6.

dijkstra找出从s出发的最短路和从t出发的最短路。

存边的时候正向和逆向分别存起来,并且在求最短路的同时计算到每个点的最短路数量。

d[0][i]表示s出发到i的最短路,d[1][i]表示t出发到i的最短路。每条边的权值为w。

则当w+d[0][u]+d[1][v]时说明是s到t的最短路上的边,如果是所有最短路都经过的边,则满足path[0][u]*path[1][v]==path[0][t]。

path是最短路的数量,因为可能爆long long,因此要取模,而且还不能是1000000007。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 #define N 100005
 7 #define M 5462617
 8 #define inf 0x3f3f3f3f3f3f3f3fll
 9 #define ll long long
10 #define add(u,v,w) e[++cnt]=(edge){v,head[0][u],w};head[0][u]=cnt;e[++cnt]=(edge){u,head[1][v],w};head[1][v]=cnt
11 using namespace std;
12 struct edge{
13     ll to,next,w;
14 }e[N<<1];
15 struct road{
16     ll u,v,w;
17 }l[N];
18 struct qnode{
19     ll v,c;
20     bool operator <(const qnode &r)const{
21         return c>r.c;
22     }
23 };
24 ll n,m,s,t,u,v,w,d[2][N],cnt,head[2][N],b[2][N],path[2][N];
25 void dijkstra(int f){
26     int i,j,k,pr=f?t:s;
27     for(i=1;i<=n;i++)d[f][i]=inf;
28     priority_queue<qnode> q;
29     d[f][pr]=0;
30     q.push((qnode){pr,0});
31     path[f][pr]=1;
32     while(!q.empty()){
33         qnode u=q.top();
34         q.pop();
35         if(b[f][u.v])continue;
36         b[f][pr=u.v]=1;
37         for(j=head[f][pr];j;j=e[j].next){
38             k=e[j].to;
39             if(d[f][pr]+e[j].w==d[f][k])
40                 path[f][k]=(path[f][k]+path[f][pr])%M;
41             else if(d[f][pr]+e[j].w<d[f][k]){
42                 d[f][k]=d[f][pr]+e[j].w;
43                 q.push((qnode){k,d[f][k]});
44                 path[f][k]=path[f][pr];
45             }
46         }
47     }
48 }
49 int main() {
50     int i,j;
51     cin>>n>>m>>s>>t;
52     for(i=1;i<=m;i++){
53         scanf("%lld%lld%lld",&u,&v,&w);
54         add(u,v,w);
55         l[i]=(road){u,v,w};
56     }
57     dijkstra(0);
58     dijkstra(1);
59     for(i=1;i<=m;i++)
60     {
61         u=l[i].u;
62         v=l[i].v;
63         w=l[i].w;
64         if(d[0][u]+d[1][v]+w==d[0][t]){
65             if(path[0][u]*path[1][v]%M==path[0][t])
66                 puts("YES");
67             else if(w>1)
68                 puts("CAN 1");
69             else puts("NO");
70         }
71         else if(d[0][u]+d[1][v]+1<d[0][t])
72             printf("CAN %lld\n",d[0][u]+d[1][v]+w-d[0][t]+1);
73         else 
74             puts("NO");
75     }
76 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【UVALive 3905】BUPT 2015 newbie practice #2 div2-D-3905 - Meteor

    http://acm.hust.edu.cn/vjudge/contest/view.action?cid=102419#problem/D

    饶文津
  • 【CodeForces 602C】H - Approximating a Constant Range(dijk)

    In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional rai...

    饶文津
  • 【Codeforces 738A】Interview with Oleg

    http://codeforces.com/contest/738/problem/A

    饶文津
  • 云存储上文件共享系统的缺陷

    云存储提供了一种更为简单的方式来私下和公开地共享文件。一个好的云存储提供商(SCP)不仅通过访问速度或可共享给他人的文件大小来衡量,而且还通过文件共享本身的安全...

    用户7724216
  • Code forces 719A Vitya in the Countryside

    A. Vitya in the Countryside time limit per test:1 second memory limit per test:2...

    Angel_Kitty
  • ZOJ 3202 Second-price Auction

    Time Limit: 1 Second      Memory Limit: 32768 KB

    ShenduCC
  • Gazebo機器人仿真學習探索筆記(一)安裝與使用

    Gazebo提供了多平臺的安裝和使用支持,大部分主流的linux,Mac以及Windows,這裏結合ROS以Ubuntu爲例進行介紹。

    zhangrelay
  • 2019-02-12 Chrome 又不能自动登录了,每次都要找方法麻烦

    Albert陈凯
  • Web前端学习(打卡机)

    在补齐了Java后端的短板之后,我准备补补前端的课。这篇文章可以作为我前端学习的过程记录(打开机)。

    阿杜
  • 论综合 | 是什么让一个数字前端实现硅农开始学习Floorplan 的?

    如题,是什么让一个数字前端实现硅农开始学习Floorplan 的?是制造工艺的进步,是实现方法学的被迫更新,是养家糊口生的本能,正可谓:头发落完终不悔,为伊消得...

    老秃胖驴

扫码关注云+社区

领取腾讯云代金券