Codeforces 567E President and Roads 【最短路】

President and Roads

Berlandhas n cities,the capital is located in city s, and thehistoric home town of the President is in city t (s ≠ t). The citiesare connected by one-way roads, the travel time for each of the road is apositive integer.

Once a year thePresident visited his historic home town t, for which hismotorcade passes along some path from s to t (he alwaysreturns on a personal plane). Since the president is a very busy man, he alwayschooses the path from s to t, along which hewill travel the fastest.

The ministry ofRoads and Railways wants to learn for each of the road: whether the Presidentwill definitely pass through it during his travels, and if not, whether it ispossible to repair it so that it would definitely be included in the shortestpath 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 thebudget, so it wants to know the minimum cost of repairing the road. Also, it isvery fond of accuracy, so it repairs the roads so that the travel time on themis always a positive integer.

Input

The first linescontain four integers n, m, s and t (2 ≤ n ≤ 105; 1 ≤ m ≤ 105; 1 ≤ s, t ≤ n) — the numberof cities and roads in Berland, the numbers of the capital and of thePresidents' home town (s ≠ t).

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

The cities arenumbered from 1 to n. Each pair of cities can have multipleroads between them. It is guaranteed that there is a path froms to t along theroads.

Output

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

If the presidentwill definitely ride along it during his travels, the line must contain asingle word "YES" (withoutthe quotes).

Otherwise, ifthe i-th road can berepaired so that the travel time on it remains positive and then president willdefinitely ride along it, print space-separated word "CAN" (withoutthe quotes), and the minimum cost of repairing.

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

Sample test(s)

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 ofrepairing the road is the difference between the time needed to ride along itbefore and after the repairing.

In the firstsample president initially may choose one of the two following ways for aride: 1 → 2 → 4 → 5 → 6 or1 → 2 → 3 → 5 → 6.

題意：

       給出一個有向圖和起終點S,T，問對于每一條邊進行詢問：，

1.     是不是一定在S-T的最短路徑上，如果是，輸出“YES”

2.     如果不是，将邊權減少多少，能讓它一定在最短路徑上，邊權值最小為1，如果可以，輸出‘CAN’ 并輸出前後的邊權差

3.     如果不能，輸出‘NO’

思路：

       就是先分别從S，T出發各跑一次Dijstra，求出各個點距離S和T的距離和最短路長度。同時記錄從S和T分别到每個點的最短路的條數，如果某邊兩端的點到S和T的最短路條數之積為從S到T的最短路條數，則該邊為必經邊，輸出“YES”；否則根據該邊兩端點到S和T的距離以及最短路的長度來決定要修改的權值，輸出“CAN”和要修改的值，如果修改之後該邊權值小于1；則輸出“NO”

       注意的到，最短路的條數相乘會很大，可能溢出，因而需要取模，這裡取的是一個比較大的素數1e9+13；

看到别人的題解裡有先把最短路取出，重建立一張無向圖，然後用tarjan算法求出哪些邊是橋。橋就是一定在最短路上的邊。但是并不會tarjan算法ORZ 有空趕緊學習了。

代碼（寫的比較挫）：

#include <bits/stdc++.h>
#define INF0x3f3f3f3f3f3f3f3f
typedef long longll;
 
using namespacestd;
const ll maxn =1e5+10;
const ll mod =1e9+13;
 
 
struct edge{
    ll v,to,cost;
    edge(ll t,ll c):to(t),cost(c){};
    edge(ll v, ll t,ll c):v(v),to(t),cost(c){};
    bool operator < (const edge & a)const{
        return cost > a.cost;
    }
};
 
vector<edge> G_a[maxn];
vector<edge> G_b[maxn];
vector<edge> e;
 
 
void addedge(llfrom, ll to, ll cost){
    G_a[from].push_back(edge(to, cost));
    G_b[to].push_back(edge(from, cost));
}
ll dis_a[maxn];
ll dis_b[maxn];
ll cnt_a[maxn];
ll cnt_b[maxn];
ll n;
 
void Dijkstra(lls,ll cnt[], ll dis[],bool flag){
    for (ll i = 0 ; i <= n ; i ++){
        dis[i] = INF;cnt[i] = 0;
    }
    dis[s] = 0;cnt[s] = 1;
    priority_queue<edge> Q;
    Q.push(edge(s,dis[s]));
    while(!Q.empty()){
        edge tmp = Q.top();Q.pop();
        ll limt =flag?G_a[tmp.to].size():G_b[tmp.to].size();
        for(ll i = 0 ; i < limt; i ++){
            edge& next = flag ?G_a[tmp.to][i]:G_b[tmp.to][i];
            if(dis[next.to] == tmp.cost+next.cost)
                cnt[next.to] =(cnt[tmp.to]+cnt[next.to])%mod;
            if(dis[next.to] > tmp.cost +next.cost){
                cnt[next.to] = cnt[tmp.to];
                dis[next.to] = tmp.cost +next.cost;
                Q.push(edge(next.to,dis[next.to]));
            }
        }
    }
}
 
int main(){
    ll m,s,t;
    cin >>n>>m>>s>>t;
    ll from, to, cos;
    for (ll i = 0 ; i < m ; i ++){
        scanf("%I64d %I64d%I64d",&from,&to,&cos);
        addedge(from,to,cos);
        e.push_back(edge(from,to,cos));
    }
    Dijkstra(s,cnt_a,dis_a,true);
    Dijkstra(t,cnt_b,dis_b,false);
    for(ll i = 0 ; i < m ; i ++){
 
       if(dis_a[e[i].v]+e[i].cost+dis_b[e[i].to] == dis_a[t] &&(cnt_a[e[i].v]*cnt_b[e[i].to])%mod == cnt_a[t])
            puts("YES");
        else{
            ll ect =dis_a[t]-dis_a[e[i].v]-dis_b[e[i].to]-1;
            if(ect < 1 || e[i].cost == 1)
                puts("NO");
            else printf ("CAN%I64d\n",e[i].cost-ect);
        }
    }
}