图给得很良心，一个s到t的有向图，权值至少为1，求出最短路，如果是一定经过的边，输出"YES"，如果可以通过修改权值，保证一定经过这条边，输出"CAN"，并且输出最小修改值，否则输出"NO"。保证有s到t的路径，可能有重边。

建正反两个图，分别求出s和t的最短路径，用来判断一条边是不是在最短路径上，然后把最短路径取出来建一个图求割边。

不要用spfa，最坏O（VE），（出卡spfa数据的方法：），会TLE 109（数据好啊），自以为是的加了个优化结果跑得更慢了，估计也是那组数据卡的吧，带重边的tarjan处理：前向星i^1!=fa,或者每条边再记录一个信息，不能用v!=fa来判断。。

#include
     
      using namespace std;typedef long long ll;#define fi first#define se second#define bug(x) cout<<#x<<'='<
      
       <
       
        dfn[u]) {                flag[id[i]] = 2;            }        }else { low[u] = min(low[u],low[v]); }    }}struct Node{    ll d;    int u;    bool operator < (const Node& x) const{        return d > x.d;    }};bool vis[maxn];void Dijkstra(int s,Graph &g){    priority_queue
        
          q;    memset(g.d,0x3f,sizeof(g.d));    g.d[s] = 0;    q.push(Node{
    0,s});    while(q.size()){        Node x = q.top(); q.pop();        int u = x.u;        if(vis[u]) continue;        vis[u] = true;        for(int i = g.head[u]; ~i; i = g.nxt[i] ){            int v = g.to[i];            if(g.d[v]> g.d[u]+g.w[i]){                g.d[v] = g.d[u]+g.w[i];                q.push(Node{g.d[v],v});            }        }    }    memset(vis,0,sizeof(vis));}#define localint main(){#ifdef local    freopen("in.txt","r",stdin);   // freopen("out.txt","w",stdout);#endif // local    int n,m,s,t;    scanf("%d%d%d%d",&n,&m,&s,&t);    for(int i = 0; i < m; i++){        int u,v,l; scanf("%d%d%d",&u,&v,&l);        G1.addEdge(u,v,l); G2.addEdge(v,u,l);    }    Dijkstra(s,G1);    Dijkstra(t,G2);    ll shortest = G1.d[t];    for(int i = 0; i < m; i++){        int u = G1.fro[i], v = G1.to[i];        if(shortest == G1.w[i] + G1.d[u] + G2.d[v] ){            id[G3.ecnt] = i; G3.addEdge(u,v,G1.w[i]);            id[G3.ecnt] = i; G3.addEdge(v,u,G1.w[i]);            flag[i] = 1;        }    }    Tarjan(s,-1);    for(int i = 0; i < m; i ++){        if(flag[i] == 2) puts("YES");        else if(flag[i] == 1){            if(G1.w[i]>1) printf("CAN 1\n");            else puts("NO");        }else {            ll detal = G1.w[i] - shortest + G1.d[G1.fro[i]]+G2.d[G1.to[i]] + 1;            if(G1.w[i] > detal)                printf("CAN %d\n",detal);            else puts("NO");        }    }    return 0;}/*自以为是的优化：    q.push(s);    while(q.size()){        int u = q.front(); q.pop();        for(int i = G1.head[u]; ~i; i = G1.nxt[i]) if(!vis[i]) {            vis[i] = true;            int v = G1.to[i];            if(G1.d[u] + G1.w[i] ==  G1.d[v] && G2.d[v] + G1.w[i] == G2.d[u]){                id[G3.ecnt] = i; G3.addEdge(u,v,G1.w[i]);                id[G3.ecnt] = i; G3.addEdge(v,u,G1.w[i]);                flag[i] = 1;                q.push(v);            }        }    }*/