\(Description\)

给定一张有向图，求哪些边一定在最短路上。对于不一定在最短路上的边，输出最少需要将其边权改变多少，才能使其一定在最短路上（边权必须为正，若仍不行输出NO）。

\(Solution\)

正反跑两遍Dijkstra。一条边\((u,v,w)\)在最短路上当且仅当\(dis[S][u]+dis[v][T]+w=dis[S][T]\)。

一定在最短路上则满足，从\(S\)走最短路到\(u\)的方案数 * 从\(v\)走最短路到\(T\)的方案数 = 从\(S\)到\(T\)的最短路径数。

也可以再对最短路上的边建图，缩点求桥。

路径数要用双模数。

//77ms  8800KB#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         //#define gc() getchar()#define MAXIN 300000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)#define mp std::make_pair#define pr std::pair
         
          #define mod 1000000007#define mod2 805306457typedef long long LL;const int N=1e5+5;int ss1[N],st1[N],ss2[N],st2[N];LL ds[N],dt[N];std::priority_queue
          
            q;char IN[MAXIN],*SS=IN,*TT=IN;struct Graph{ int Enum,H[N],nxt[N],fr[N],to[N],len[N]; inline void AE(int u,int v,int w) { to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w; }}G,R;inline int read(){ int now=0;register char c=gc(); for(;!isdigit(c);c=gc()); for(;isdigit(c);now=now*10+c-'0',c=gc()); return now;}void Dijkstra(int S,int T,int *sum,int *sum2,LL *dis,const Graph &g){ static bool vis[N]; memset(vis,0,sizeof vis); memset(dis,0x3f,sizeof ds); dis[S]=0, sum[S]=sum2[S]=1, q.push(mp(0,S)); while(!q.empty()) { int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=g.H[x],v; i; i=g.nxt[i]) if(dis[v=g.to[i]]>dis[x]+g.len[i]) sum[v]=sum[x], sum2[v]=sum2[x], q.push(mp(-(dis[v]=dis[x]+g.len[i]),v)); else if(dis[v]==dis[x]+g.len[i]) sum[v]+=sum[x], sum[v]>=mod&&(sum[v]-=mod), sum2[v]+=sum2[x], sum2[v]>=mod2&&(sum2[v]-=mod2); }}int main(){ int n=read(),m=read(),S=read(),T=read(); for(int i=1,u,v,w; i<=m; ++i) u=read(),v=read(),w=read(),G.AE(u,v,w),R.AE(v,u,w); Dijkstra(S,T,ss1,ss2,ds,G), Dijkstra(T,S,st1,st2,dt,R); for(int p=1,u,v,w; p<=m; ++p) { u=G.fr[p],v=G.to[p],w=G.len[p]; if(ds[u]+w+dt[v]==ds[T] && 1ll*ss1[u]*st1[v]%mod==ss1[T] && 1ll*ss2[u]*st2[v]%mod2==ss2[T]) puts("YES"); else if(ds[T]-ds[u]-dt[v]-1>0) printf("CAN %I64d\n",-(ds[T]-ds[u]-dt[v])+w+1); else puts("NO"); } return 0;}