比较简答的回路判断
我们把最后的几个是虫洞的单向路的W权值置为负数,其他的就是模板啦
// AC 248k 141ms #include<cstdio> #include<queue> using namespace std; struct node { int to,time,next; }edge[5202]; int head[502]; int tol; void add(int st,int end,int time) { edge[tol].time=time; edge[tol].to=end; edge[tol].next=head[st]; head[st]=tol++; } int N,M,W; void init() { int i; scanf("%d%d%d",&N,&M,&W); tol=0; for(i=1;i<=N;i++) head[i]=-1; int a,b,c; for(i=0;i<M;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c);add(b,a,c); } for(i=0;i<W;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } } int d[502],cnt[502]; bool flag[502]; bool spfa() { int i; for(i=1;i<=N;i++) cnt[i]=0,flag[i]=false,d[i]=5000005; d[1]=0; queue<int>q; cnt[1]++; q.push(1); while(!q.empty()) { int u=q.front();q.pop();flag[u]=false; for(int j=head[u];j!=-1;j=edge[j].next) { int v=edge[j].to,w=edge[j].time; if(d[v] > d[u]+w) { d[v]=d[u]+w; if(!flag[v]) flag[v]=true,cnt[v]++,q.push(v); if(cnt[v] > N) return true;//回路 } } } return false; } int main() { int F; scanf("%d",&F); while(F--) { init(); if(spfa()) printf("YES\n"); else printf("NO\n"); } return 0; }