很套路的题啊, 见过很多次了。
#include<bits/stdc++.h> #define LL long long #define LD long double #define ull unsigned long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ALL(x) (x).begin(), (x).end() #define fio ios::sync_with_stdio(false); cin.tie(0); using namespace std; const int N = 1e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-8; const double PI = acos(-1); template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;} template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;} template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;} template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;} int n, m, s, t; int a[N], b[N], l[N], cnt[N], ans[N]; LL d[2][N]; vector<vector<PLI>> G, rG, tG; void dij(int s, LL d[N], vector<vector<PLI>> &G) { priority_queue<PLI, vector<PLI>, greater<PLI> > que; d[s] = 0; que.push(mk(0, s)); while(!que.empty()) { int u = que.top().se; LL dis = que.top().fi; que.pop(); if(dis > d[u]) continue; for(auto &e : G[u]) { if(chkmin(d[e.se], dis + e.fi)) { que.push(mk(d[e.se], e.se)); } } } } int dfn[N], low[N], idx; void tarjan(int u, int id) { dfn[u] = low[u] = ++idx; for(auto &e : tG[u]) { if(e.fi == id) continue; if(!dfn[e.se]) { tarjan(e.se, e.fi); low[u] = min(low[u], low[e.se]); if(dfn[u] < low[e.se]) ans[e.fi] = 0; } else low[u] = min(low[u], dfn[e.se]); } } int main() { memset(d, 0x3f, sizeof(d)); scanf("%d%d%d%d", &n, &m, &s, &t); G.resize(n + 1); rG.resize(n + 1); tG.resize(n + 1); for(int i = 1; i <= m; i++) { scanf("%d%d%d", &a[i], &b[i], &l[i]); G[a[i]].push_back(mk(l[i], b[i])); rG[b[i]].push_back(mk(l[i], a[i])); } dij(s, d[0], G); dij(t, d[1], rG); for(int i = 1; i <= m; i++) { if(d[0][a[i]] + d[1][b[i]] + l[i] >= INF) { ans[i] = -1; } else { if(d[0][a[i]] + d[1][b[i]] + l[i] == d[0][t]) { tG[a[i]].push_back(mk(i, b[i])); tG[b[i]].push_back(mk(i, a[i])); } ans[i] = d[0][a[i]] + d[1][b[i]] + l[i] + 1 - d[0][t]; } } for(int i = 1; i <= n; i++) { if(!dfn[i]) { tarjan(i, 0); } } for(int i = 1; i <= m; i++) { if(ans[i] == -1 || l[i] - ans[i] <= 0) puts("NO"); else if(ans[i] == 0) puts("YES"); else printf("CAN %d\n", ans[i]); } return 0; } /* */