题意：
农夫约翰农场里发现了很多虫洞，他是个超级冒险迷，想利用虫洞回到过去，看再回来的时候能不能看到没有离开之前的自己，农场里有N块地，M条路连接着两块地，W个虫洞，连接两块地的路是双向的，而虫洞是单向的，去到虫洞之后时间会倒退T秒，如果能遇到离开之前的自己就输出YES，反之就是NO。
分析：
就是求一幅图中有没有负权环路， 可以bellman n-1次后再跑一次看看能不能更新， 能更新说明有环。
也可以spfa记录入队次数， 入队次数大于等于N说明有负权环路
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #define rep(i,a,b) for(int i = a; i < b; i++) #define _rep(i,a,b) for(int i = a; i <= b; i++) using namespace std; #define inf 0x3f3f3f3f const int maxn = 1000, maxm = 10000; int N,M,W; struct E { int v, time, nxt; }Edge[maxm]; int cnt = 0; int head[maxn], enter_cnt[maxn]; int dis[maxn], vis[maxn]; void add_edge(int u , int v, int d){ Edge[cnt].v = v; Edge[cnt].time = d; Edge[cnt].nxt = head[u]; head[u] = cnt++; } bool spfa(){ fill(dis, dis+maxn, inf); memset(vis, 0, sizeof(vis)); memset(enter_cnt, 0, sizeof(enter_cnt)); queue<int> q; q.push(1); dis[1] = 0; vis[1] = 1; enter_cnt[1]++; while(!q.empty()){ int u = q.front(); for(int i = head[u]; i != -1; i = Edge[i].nxt){ int v = Edge[i].v, d = Edge[i].time; if(dis[v] > dis[u] + d){ if(++enter_cnt[v] >= N) return false; //如果入队次数 >= N， 那么一定有负权环路 dis[v] = dis[u] + d; if(!vis[v]){ vis[v] = 1; q.push(v); } } } vis[u] = 0; q.pop(); } return true; } int main() { int T; scanf("%d", &T); while(T--) { memset(head, -1, sizeof(head)); cnt = 0; scanf("%d %d %d", &N, &M, &W); for(int i = 0; i < M; i++) { int tu,tv,tt; scanf("%d %d %d", &tu, &tv, &tt); add_edge(tu,tv,tt); add_edge(tv,tu,tt); } for(int i = 0; i < W; i++) { int tu,tv,tt; scanf("%d %d %d", &tu, &tv, &tt); add_edge(tu,tv,-tt); } if(!spfa()) printf("YES "); else printf("NO "); } }