判断YES的情况，直接用最短路计数判断即可。
对于CNT的情况判断和最短路的差值，示范法能被减掉即可。
其他情况就是NO
注意，codeforces卡单模数，所以可以用随机模数。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; mt19937 rnd(time(0)); int n,m,s,t,d1[N],d2[N],cnt1[N],cnt2[N],a[N],b[N],c[N],mod; vector<pair<int,int> > g1[N],g2[N]; void Dijkstra(int s,int t,int d[],int cnt[],vector<pair<int,int> > g[]){ d[s]=0; cnt[s]=1; int vis[N]={0}; priority_queue<pair<int,int> > q; q.push({0,s}); while(q.size()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(auto to:g[u]) if(d[to.first]>d[u]+to.second){ d[to.first]=d[u]+to.second; cnt[to.first]=cnt[u]; q.push({-d[to.first],to.first}); }else if(d[to.first]==d[u]+to.second) cnt[to.first]=(cnt[to.first]+cnt[u])%mod; } } signed main(){ cin>>n>>m>>s>>t; mod=rnd()%(100000000)+13; for(int i=1;i<=m;i++){ scanf("%lld %lld %lld",&a[i],&b[i],&c[i]); g1[a[i]].push_back({b[i],c[i]}),g2[b[i]].push_back({a[i],c[i]}); } memset(d1,0x3f,sizeof d1),memset(d2,0x3f,sizeof d2); Dijkstra(s,t,d1,cnt1,g1),Dijkstra(t,s,d2,cnt2,g2); for(int i=1;i<=m;i++){ if(d1[a[i]]+d2[b[i]]+c[i]==d1[t]){ if(cnt1[a[i]]*cnt2[b[i]]%mod==cnt1[t]) puts("YES"); else if(c[i]>1) puts("CAN 1"); else puts("NO"); }else{ int tmp=d1[a[i]]+d2[b[i]]+c[i]; if(c[i]>tmp-d1[t]+1) printf("CAN %d\n",tmp-d1[t]+1); else puts("NO"); } } return 0; }