在探索他的许多农场时，农夫约翰发现了许多惊人的虫洞。虫洞非常奇特，因为它是一条单行道，在你进入虫洞之前的时间将你送到目的地！FJ的每个农场都包括N（1≤N≤500）田地，编号为1。N，M（1 ≤ M ≤ 2500）路径和W（1 ≤ W ≤200）虫洞。
由于FJ是一个狂热的时间旅行爱好者，他想做以下事情：从某个场地开始，穿过一些路径和虫洞，并在他最初离开之前的时间返回起跑场。也许他能够:)见到自己。
为了帮助FJ了解这是否可能，他将为您提供其农场F（1 ≤ F ≤ 5）的完整地图。任何路径都不会花费超过10，000秒的时间来行驶，也没有虫洞可以将FJ带回超过10，000秒的时间。
ac代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 100010
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, w;
int head[MAXN], ed[MAXN], val[MAXN], nex[MAXN], idx;
int dist[MAXN], vis[MAXN], cnt[MAXN];
void add(int x, int y, int z) {//链式前向星储路径ed[idx] = y;val[idx] = z;nex[idx] = head[x];head[x] = idx++;
}
int spfa()
{int i;memset(dist, 0x3f, sizeof(dist));//初始化距离为无穷大memset(vis, 0, sizeof(vis));//队列中标记为1，不在队列中为0memset(cnt, 0, sizeof(cnt));//表示当前点到起点最短路的边数，初始化为0个；queue<int> q;//队列for (i = 1; i <= n; i++){vis[i] = 1;//准备放入队列，标记q.push(i);//把所有点作为初始点塞进队列}while (q.size() > 0) {//几乎就是spfa算法了。int temp = q.front();q.pop();vis[temp] = 0;for (int i = head[temp]; i != -1; i = nex[i]) {if (dist[ed[i]] > dist[temp] + val[i]) {dist[ed[i]] = dist[temp] + val[i];cnt[ed[i]] = cnt[temp] + 1;if (cnt[ed[i]] >= n)return 1;if (vis[ed[i]] == 0) {q.push(ed[i]);vis[ed[i]] = 1;}}}}return 0;
}int main() {int t;scanf("%d", &t);while (t--){memset(head, -1, sizeof(head));scanf("%d %d %d", &n, &m, &w);for (int i = 1; i <= m; i++) {int x, y, z;scanf("%d %d %d", &x, &y, &z);add(x, y, z);add(y, x, z);//双向}for (int i = 1; i <= w; i++){int x, y, z;scanf("%d %d %d", &x, &y, &z);add(x, y, -z);//虫洞是回溯时间，z为-的；}int res = spfa();if (res == 1)printf("YES\n");//有一次还把大小写看错了，啊这else printf("NO\n");}return 0;
}这里呢，我再展示下我的超时代码，ac代码思路是受大佬启发的，下面代码是我最初的想法。
#include<iostream>//超时代码
#include<cstring>
#include<algorithm>
#include<queue>#define MAXN 100010using namespace std;const int inf = 0x3f3f3f3f;
int n, m,w;
int head[MAXN], ed[MAXN], val[MAXN], nex[MAXN], idx;
int dist[MAXN], vis[MAXN], cnt[MAXN];void add(int x, int y, int z) {ed[idx] = y;val[idx] = z;nex[idx] = head[x];head[x] = idx++;
}int spfa() {int i;for (i = 1; i <= n; i++)、、(是我心存侥幸了){int start = i;memset(dist, 0x3f, sizeof(dist));memset(vis, 0, sizeof(vis));memset(cnt, 0, sizeof(cnt));dist[start] = 0;vis[start] = 1;queue<int> q;q.push(start);while (q.size() > 0) {int temp = q.front();q.pop();vis[temp] = 0;for (int i = head[temp]; i != -1; i = nex[i]) {if (dist[ed[i]] > dist[temp] + val[i]) {dist[ed[i]] = dist[temp] + val[i];cnt[ed[i]] = cnt[temp] + 1;if (cnt[ed[i]] >= n)return 1;if (vis[ed[i]] == 0) {q.push(ed[i]);vis[ed[i]] = 1;}}}}}return 0;
}int main() {int t;scanf("%d", &t);while (t--){memset(head, -1, sizeof(head));scanf("%d %d %d", &n, &m, &w); for (int i = 1; i <= m; i++) {int x, y, z;scanf("%d %d %d", &x, &y, &z);add(x, y, z);add(y, x, z);}for (int i = 1; i <= w; i++){int x, y, z;scanf("%d %d %d", &x, &y, &z);add(x, y, -z);}int res = spfa();if (res == 1)printf("YES\n");else printf("NO\n");}return 0;
}
