先放图
题目
题目背景
题目描述
Farmer John 在探索他的农场时发现了许多神奇的虫洞。虫洞的特性非常特殊——它是一个单向通道，能将你传送到它的目的地，而且时间还会回溯到过去！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 秒前。
输入格式
第 1 行：一个整数 F，表示农场数。后续为 F 个农场的数据。
每个农场：
第 1 行：三个空格分隔的整数 N（田地数）, M（双向路径数）, W（虫洞数）。
第 2∼M+1 行：每行三个空格分隔的整数 (S,E,T)，表示 S 和 E 间有一条耗时 T 秒的双向路径。两块田地间可能存在多条路径。
第 M+2∼M+W+1 行：每行三个空格分隔的整数 (S,E,T)，表示一条从 S 到 E 的单向虫洞，可将 FJ 带回 T 秒前。
输出格式
输出 F 行：对每个农场，若 FJ 能达成目标输出YES，否则输出NO。
输入输出样例
输入 #1
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8输出 #1
NO
YES说明/提示
农场 1：FJ 无法实现时间回溯。
农场 2：FJ 可通过环 1→2→3→1 回到起点 1 秒前（可从环上任意点出发实现）。
翻译：DeepSeek-R1
思路
题目解析
这是一道SPFA板子题，题目大意可以理解为：
有 NN个点
有 MM条双向边，经过会增加时间
有 WW条单向边，经过可以减少时间（
穿越了）
然后这是一道多组测试数据的题，有 FF组数据
题目需要你求出，从任意一点出发，会不会遇到负环（因为有负环，所以FJ可以回到起点），有就输出 YES ，没有也就是FJ没法回到起点，输出 NO
代码构思
首先注意到我们可以从任意点出发，所以我们需要建一个 超级源点， 有了超级源点后，我们跑SPFA从超级源点出发，这样就可以到达所有点，避免了跑很多遍SPFA来求最优解。那么超级源点是什么呢？就是一个点，比如点0，连接了其他所有点，然后每条连接的边都是单向边，且花费为0，这里我们搭配图片理解：
然后就是SPFA求负环的板子了，不知道SPFA怎么求负环的可以看看这篇文章，里面有讲SPFA如何求负环，那么最终代码如下：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500 + 5;
int T;
int n, m, mm;
vector<vector<pair<int, int>>> e; // 奇葩STL，不喜欢可以写结构体，会麻烦点
ll dis[N]; // 没啥用的距离数组，辅助求负环
bool vis[N]; // 标记任意点是否在队列中
int cnt[N]; // 标记任意点的使用次数，用来求负环
bool spfa() {
// 初始化
fill(dis + 1, dis + n + 1, INT_MAX);
fill(cnt + 1, cnt + n + 1, 0);
fill(vis + 1, vis + n + 1, false);
queue<int> q;
q.emplace(0);
dis[0] = 0;
vis[0] = true;
// SPFA板子
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = false;
for (auto tmp : e[u]) { // 适配C++14的写法
int v, w;
tie(v, w) = tmp;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1; // 求负环
if (cnt[v] > n) return false; // 多了一个超级源点，所以是大于n，有负环
if (!vis[v]) {
vis[v] = true;
q.emplace(v);
}
}
}
}
return true; //没有负环
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
// 因为有多组数据，每次e数组清空，然后重设大小
e.clear();
e.resize(N);
cin >> n >> m >> mm;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w; // 输入普通的双向边
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
for (int i = 1; i <= mm; ++i) {
int u, v, w;
cin >> u >> v >> w; // 输入虫洞
e[u].emplace_back(v, -w);
}
// 超级源点
for (int i = 1; i <= n; ++i) {
e[0].emplace_back(i, 0); // 建立单向边，将0指向其他所有点，且花费为0
}
cout << (spfa() ? "NO" : "YES") << "\n"; // 有负环就是可以回到起点，输出YES，否则是NO
}
return 0;
}