poj 3259 Wormholes(最短路 Bellman)

题意：一个famer有一些农场，这些农场里面有一些田地，田地里面有一些虫洞，田地和田地之间有路，虫洞有这样的性质：时间倒流。问你这个农民能不能看到他自己，也就是说，有没有这样一条路径，能利用虫洞的时间倒流的性质，让这个人能在这个点出发前回去，这样他就是能看到他自己

典型的Bellman_ford 检查有没有形成负环。

套的模板

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 const int maxn = 1011;
 5 const int maxm = 10011;
 6 const int oo = 1<<28;
 7 struct node{
 8     int u;
 9     int v;
10     int w;
11     int next;
12 }edge[maxm];
13 int dis[maxn];
14 int cnt;
15 int n, m;
16 
17 void add(int u, int v, int w){
18     edge[cnt].u = u;
19     edge[cnt].v = v;
20     edge[cnt++].w = w;
21 }
22 
23 bool bellman_ford(int s){
24     for(int i = 0; i < n; i++){
25         dis[i] = oo;
26     }
27     dis[s] = 0;
28     for(int i = 0; i < n-1; i++){
29         for(int j = 0; j < cnt; j++){
30             int u = edge[j].u;
31             int v = edge[j].v;
32             int w = edge[j].w;
33             if(dis[v] > dis[u] + w){
34                 dis[v] = dis[u] + w;
35             }
36         }
37     }
38     for(int j = 0; j < cnt; j++){
39         int u = edge[j].u;
40         int v = edge[j].v;
41         int w = edge[j].w;
42         if(dis[v] > dis[u] + w){
43             return false;
44         }
45     }
46     return true;
47 }
48 
49 void init(){
50     cnt = 0;
51 }
52 
53 int main()
54 {
55     int t,x;
56     scanf("%d",&t);
57     while(t--)
58     {
59     scanf("%d %d %d", &n, &m, &x);
60         int u, v, w;
61         init();
62         for(int i = 0; i < m; i++){
63             scanf("%d %d %d", &u, &v, &w);
64             add(u, v, w);
65             add(v, u, w);
66         }
67         while(x--)
68         {
69             scanf("%d %d %d", &u, &v, &w);
70             add(u, v, -w);
71         }
72         if(bellman_ford(1)) printf("NO
");
73         else printf("YES
");
74     }
75     return 0;
76 }

discuss里面还有spfa 的代码：http://poj.org/showmessage?message_id=162146

就是又设了一个cnt数组来记录各个点用过的次数，如果次数大于等于n说明有负环