差分约束系统zoj2770

 1 #include 
 2 #define INF 9999999
 3 #define N 1001
 4 #define E 23000
 5 int d[N],c[N],x[N],s[N];
 6 int n,m;
 7 int dist[N];
 8 struct edge{
 9     int u,v,w;
10 }e[E];
11 int edgeNum;
12 void add(int u,int v,int w){
13     e[edgeNum].u=u;
14     e[edgeNum].v=v;
15     e[edgeNum++].w=w;
16 }
17 bool bellman(){
18     int i,j;
19     for(i=1;iINF;
20     for(i=0;i){
21         for(j=0;j)
22             if(dist[e[j].u]!=INF&&dist[e[j].u]+e[j].w<dist[e[j].v]){
23                 dist[e[j].v]=dist[e[j].u]+e[j].w;
24             }
25     }
26     for(int j=0;j)
27         if(dist[e[j].u]!=INF&&dist[e[j].u]+e[j].w<dist[e[j].v])
28             return 0;
29     return 1;
30 }
31 int main(){
32     int i,j,k;
33     while(scanf("%d%d",&n,&m)!=EOF){
34         edgeNum=0;
35         d[n]=dist[0]=0;
36         for(i=1;i<=n;i++){
37             scanf("%d",&c[i]);
38             add(i-1,i,c[i]);
39             add(i,i-1,0);
40             d[i]=d[i-1]+c[i];
41         }
42         while(m--){
43             scanf("%d%d%d",&i,&j,&k);
44             add(j,i-1,-k);
45             add(i-1,j,d[j]-d[i-1]);
46         }
47         if(!bellman()) puts("Bad Estimations");
48         else printf("%d\n",dist[n]-dist[0]);
49     }
50     return 0;
51 }