差分约束，第一次听说这个东西，看来以前知道的还是太少了，惭愧

代码是别人的，看了几遍看懂了，贴过来，转载一下

利用Bellaman Ford最短路算法，这个算法也是第一次听说……

要学的东西好多～

http://acm.oopos.cn/sutu.htm

一个牛人的解题报告，没太看懂，写的有点乱


 1 #include<string>
 2 #include<iostream>
 3 using namespace std;
 4 const int M = 100001;
 5 int n, mx, my, d[M];
 6 
 7 struct edge
 8 {
 9           int u, v, w;
10 
11 }e[M];
12 
13 
14 // d[v] <= d[u] - w           [1]
15 // d[i] <= d[i - 1] + 1        [2]
16 // d[i - 1] <= d[i]              [3]
17 
18 int bellman( )
19 {
20           int i, k;
21           bool flag = true;
22           while( flag )
23           {
24                   flag = false;
25                   for ( i = 0; i < n; i++ )
26                   {
27                            k = d[e[i].u] + e[i].w;
28                            if ( k < d[e[i].v] )
29                                    d[e[i].v] = k, flag = 1;
30                   }
31 
32                  for ( i = mx; i <= my; i++ )
33                         if ( d[i-1] + 1 < d[i] )
34                                d[i] = d[i-1] + 1, flag = 1;
35 
36                 for ( i = my; i >= mx; i-- )
37                        if ( d[i-1] > d[i] )
38                                d[i-1] = d[i], flag = 1;
39 
40           }
41           return d[my] - d[mx - 1];
42 }
43 
44 int main ()
45 {
46            int i, j, k, l;
47            while ( scanf("%d", &n) != EOF )
48            {
49                    memset(d, 0, sizeof(d));
50                    mx = M, my = 0;
51                    for ( i = 0; i < n; i++ )
52                    {
53                             scanf("%d%d%d", &j, &k, &l);
54                             e[i].u = k;
55                             e[i].v = j - 1;
56                             e[i].w = -l;
57                             if ( mx > j ) mx = j;//
58                             if ( my < k ) my = k;//
59                     }
60                     printf("%d\n", bellman() );
61            }
62            return 0;
63 }