Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes. As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) . To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
【题目分析】 按题目要求建图，然后就是判负环了。Bellman Ford算法，最好写了。
【代码】
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int fr[100001],to[100001],w[100001],dis[100001]; int n,m,mm,en; inline bool BF() { memset(dis,0x3f,sizeof dis); dis[1]=0; for (int k=1;k<=m+mm;++k) for (int i=1;i<=en;++i) dis[to[i]]=min(dis[to[i]],dis[fr[i]]+w[i]); // for (int i=1;i<=n;++i) cout<<dis[i]<<" "; // cout<<endl; for (int i=1;i<=en;++i) if (dis[to[i]]>dis[fr[i]]+w[i]) return true; return false; } int main() { int tt; scanf("%d",&tt); while (tt--) { en=0; scanf("%d%d%d",&n,&m,&mm); for (int i=1;i<=m;++i) { int a,b,c; scanf("%d%d%d",&a,&b,&c); fr[++en]=a;to[en]=b;w[en]=c; fr[++en]=b;to[en]=a;w[en]=c; } for (int i=1;i<=mm;++i) { int a,b,c; scanf("%d%d%d",&a,&b,&c); fr[++en]=a;to[en]=b;w[en]=-c; } if (BF()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }