题意：John的农场里n块地，m条路连接两块地，m条路是双向的。w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。
思路：Bellman-Ford。由于存在负权边，Dijkstra便不能用了。题目简化下，就是看图中有没有负权环，有的话John可以无限次走这个环，使得时间一定能得到一个负值。所以有的存在负环话就是可以，没有的话就是不可以了。
Bellman算法：最短路径就是不断的松弛的操作，如果存在最短路，那么最多经过n-1个点，我们先松弛n-1次， 然后看看能不能再做松弛操作，如果可以松弛就代表图存在负环。
#include#include #include using namespace std; struct Edge { int s, e; int v; }e[5210]; int dis[1001]; int n, m, w; int all; bool Bellman() { memset(dis, 0x3f, sizeof(dis)); for (int i = 1; i < n; i++) { int hasrelax = false; for (int j = 1; j <= all; j++) { int u = e[j].s; int v = e[j].e; int t = e[j].v; if (dis[v] > dis[u]+t) { dis[v] = dis[u]+t; hasrelax = true; } } if (hasrelax == false) break; } for (int j = 1; j <= all; j++) { int u = e[j].s; int v = e[j].e; int t = e[j].v; if (dis[v] > dis[u]+t) return true; } return false; } int main() { int f; scanf("%d", &f); while (f--) { all = 0; scanf("%d %d %d", &n, &m, &w); int u, v, t; for (int i = 1; i <= m; i++) { scanf("%d %d %d", &u, &v, &t); e[++all].s = u; e[all].e = v; e[all].v = t; e[++all].s = v; e[all].e = u; e[all].v = t; } for (int i = 1; i <= w; i++) { scanf("%d %d %d", &u, &v, &t); e[++all].s = u; e[all].e = v; e[all].v = -t; } if (Bellman()) puts("YES"); else puts("NO"); } return 0; }