题目描述
教学楼里有很多教室，这些教室由双向走廊连接。另外，还存在一些单向的秘密通道，通过它们可以回到过去。现在有 N (1 ≤ N ≤ 500) 个教室，编号 1…N, M (1 ≤ M ≤ 2500) 条走廊，和 W (1 ≤ W ≤ 200) 条秘密通道。
DY在养猫之余，还是一个时间旅行爱好者。她希望从一间教室出发，经过一些走廊和秘密通道，回到她出发之前的某个时间。
共有F (1 ≤ F ≤ 5) 组数据。对每组数据，判断DY是否有回到过去的可能性。不存在耗时超过10,000秒的走廊，且不存在能带DY回到10,000秒之前的秘密通道。
输入格式
首先是一个整数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可以使时间倒流T秒。
输出格式
F行，每行对应一组数据。 每组数据输出单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求。
输入样例
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
输出样例
NO
YES
题目大意：
输入 f 表示有 f 组测试用例，对于每组测试样例先输入n, m, w, 表示一共有n个教师，m条双向走廊，和 w 个虫洞，然后输入输入m条路和w个虫洞，对于每条走廊，a b c 表示a b之间有一条双向走廊，穿过需要c秒，对于虫洞，a b c 表示 a b 有一条单向虫洞，每次经过都会使时间回溯c 秒，询问是否能通过虫洞回到原点，见到没出发时的自己。
解题思路：
建图时将虫洞的权重建成负的，抽象成判负环的过程，因为只要存在负环，就能不断松弛，这里注意一下建图，跑spfa判负环即可。
Code：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 50;
const int M = 1e4 + 50;
int h[N], ne[M], w[M], e[M], idx;
int f, n, m, p;
int dis[N], cnt[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
void init()
{
idx = 0;
memset(h, -1, sizeof h);
memset(dis, 0x3f, sizeof dis);
memset(cnt, 0, sizeof cnt);
}
bool spfa()
{
queue<int > q;
for (int i = 1; i <= n; i ++)
{
q.push(i);
vis[i] = true;
}
while (!q.empty())
{
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dis[t] + w[i] < dis[j])
{
dis[j] = dis[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!vis[j])
{
q.push(j);
vis[j] = true;
}
}
}
}
return false;
}
int main()
{
scanf("%d", &f);
while (f --)
{
init();
scanf("%d%d%d", &n, &m, &p);
while (m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
while (p --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, -c);
}
puts(spfa() ? "YES" : "NO");
}
return 0;
}