poj 1201 Intervals(差分约束)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 using namespace std;
 7 
 8 const int INF = 1<<28;
 9 struct node
10 {
11     int u;
12     int v;
13     int w;
14     int next;
15 }edge[50010];
16 int dis[50010];
17 int mi,ma,n;
18 
19 void bellman_ford()
20 {
21    int i,f=1;
22    while(f)
23    {
24        f=0;
25        for(i=1; i<=n; i++)
26        if(dis[edge[i].u]>dis[edge[i].v]-edge[i].w)
27        {
28            dis[edge[i].u]=dis[edge[i].v]-edge[i].w;
29            f=1;
30        }
31 
32        for(i=mi; i<=ma; i++)
33        if(dis[i]>dis[i-1]+1)
34        {
35            dis[i]=dis[i-1]+1;
36            f=1;
37        }
38 
39        for(i=ma; i>=mi; i--)
40        if(dis[i-1]>dis[i])
41        {
42            dis[i-1]=dis[i];
43            f=1;
44        }
45    }
46 }
47 
48 int main()
49 {
50     int i;
51     while(~scanf("%d",&n))
52     {
53         mi=INF;  ma=-1;
54         for(i=1; i<=n; i++)
55         {
56             scanf("%d%d%d",&edge[i].u, &edge[i].v, &edge[i].w);
57             if(mi>edge[i].u)
58             mi=edge[i].u;
59             if(ma<edge[i].v)
60             ma=edge[i].v;
61 
62             edge[i].u--;
63             dis[i]=0;
64         }
65         bellman_ford();
66        printf("%d\n",dis[ma]-dis[mi-1]);
67     }
68     return 0;
69 }