大意：虫洞旅行，前面一部分（n组）是双向正权，后面一部分（w组）是单向负权，判断有没有负权环。
思路：由于有负权边，就不能Dijkstra了，用Bellman_Ford。就是看图中有没有负权环，有的话可以无限次走这个环，使得时间一定能得到一个负值。所以有的存在负环话就是可以，没有的话就是不可以了。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #define Max = 10001 5 6 struct node 7 { 8 int s, e, t; 9 } q[5010]; 10 11 int dis[520]; 12 13 bool Bellman_Ford(int n, int r) 14 { 15 memset(dis, 0, sizeof(dis)); 16 for(int i = 1; i <= n; i++) 17 { 18 bool flag = false; 19 for(int j = 1; j <= r; j++) 20 { 21 if(dis[q[j].e] > dis[q[j].s]+q[j].t) 22 { 23 dis[q[j].e] = dis[q[j].s]+q[j].t; 24 flag = true; 25 } 26 } 27 if(!flag) 28 { 29 break; 30 } 31 } 32 for(int i = 1; i <= r; i++) 33 { 34 if(dis[q[i].e] > dis[q[i].s]+q[i].t) 35 { 36 return true; 37 } 38 } 39 return false; 40 } 41 42 void Solve() 43 { 44 int p, n, m, w, a, b, c; 45 scanf("%d", &p); 46 while(p--) 47 { 48 scanf("%d%d%d", &n, &m, &w); 49 int r = 0; 50 for(int i = 1; i <= m; i++) 51 { 52 scanf("%d%d%d", &a, &b, &c); 53 q[++r].s = a; 54 q[r].e = b; 55 q[r].t = c; 56 q[++r].s = b; 57 q[r].e = a; 58 q[r].t = c; 59 } 60 for(int i = 1; i <= w; i++) 61 { 62 scanf("%d%d%d", &a, &b, &c); 63 q[++r].s = a; 64 q[r].e = b; 65 q[r].t = -c; 66 } 67 if(Bellman_Ford(n, r)) 68 { 69 printf("YES "); 70 } 71 else 72 { 73 printf("NO "); 74 } 75 } 76 } 77 78 int main() 79 { 80 Solve(); 81 82 return 0; 83 }