poj3519

凡是差分约束系统的题目
都是转化为d[j]-d[i]<=w[i,j]的形式
然后我们建立边i-->j 边权为w[i,j]
对于这道题，要求d[n]-d[1]尽可能的大
设d[i]为相对差，d[1]=0，我们只要跑1-->n的最短路即可（为什么是最短路呢？实在不明白简单举一个例子即可）
由于这道题边不存在负权，所以我们用dij+heap更合适

  1 const inf=2147483647;
  2 type link=^node;
  3      node=record
  4        po,len:longint;
  5        next:link;
  6      end;
  7      point=record
  8        num,loc:longint;
  9      end;
 10 
 11 
 12 var w:array[0..30010] of link;
 13     heap:array[0..30010] of point;
 14     where,d:array[0..30010] of longint;
 15     z,t,s,i,j,n,m,x,y:longint;
 16     p:link;
 17 
 18 function min(a,b:longint):longint;
 19   begin
 20     if a>b then exit(b) else exit(a);
 21   end;
 22 
 23 procedure swap(var a,b:point);
 24   var c:point;
 25   begin
 26     c:=a;
 27     a:=b;
 28     b:=c;
 29   end;
 30 
 31 procedure add(x,y,z:longint);
 32   var p:link;
 33   begin
 34     new(p);
 35     p^.po:=y;
 36     p^.len:=z;
 37     p^.next:=w[x];
 38     w[x]:=p;
 39   end;
 40 
 41 procedure up(i:longint);
 42   var j,x,y:longint;
 43   begin
 44     j:=i shr 1;
 45     while j>0 do
 46     begin
 47       if heap[i].num<heap[j].num then
 48       begin
 49         x:=heap[i].loc;
 50         y:=heap[j].loc;
 51         where[x]:=j;
 52         where[y]:=i;
 53         swap(heap[i],heap[j]);
 54         i:=j;
 55         j:=i shr 1;
 56       end
 57       else break;
 58     end;
 59   end;
 60 
 61 procedure sift(i:longint);
 62   var j,x,y:longint;
 63   begin
 64     j:=i shl 1;
 65     while j<=s do
 66     begin
 67       if (j+1<=s) and (heap[j].num>heap[j+1].num) then inc(j);
 68       if heap[i].num>heap[j].num then
 69       begin
 70         x:=heap[i].loc;
 71         y:=heap[j].loc;
 72         where[x]:=j;
 73         where[y]:=i;
 74         swap(heap[i],heap[j]);
 75         i:=j;
 76         j:=i shl 1;
 77       end
 78       else break;
 79     end;
 80   end;
 81 
 82 procedure dij;
 83   var p:link;
 84       mid,k,y:longint;
 85   begin
 86     p:=w[1];
 87     for i:=2 to t do
 88       d[i]:=inf;
 89     d[1]:=0;
 90     while p<>nil do
 91     begin
 92       x:=p^.po;
 93       d[x]:=min(d[x],p^.len);
 94       p:=p^.next;
 95     end;
 96     s:=0;
 97     for i:=2 to t do
 98     begin
 99       inc(s);
100       heap[s].num:=d[i];
101       heap[s].loc:=i;
102       where[i]:=s;
103       up(s);
104     end;
105 
106     for k:=1 to t do
107     begin
108       mid:=heap[1].num;
109       if s=0 then break;
110       if mid=inf then break;
111       x:=heap[1].loc;
112       y:=heap[s].loc;
113       where[y]:=1;
114 
115       swap(heap[1],heap[s]);
116       dec(s);
117 
118       sift(1);
119       p:=w[x];
120       while p<>nil do
121       begin
122         y:=p^.po;
123         if d[y]>p^.len+mid then
124         begin
125           d[y]:=p^.len+mid;
126           heap[where[y]].num:=d[y];
127           up(where[y]);
128         end;
129         p:=p^.next;
130       end;
131     end;
132   end;
133 
134 begin
135   readln(t,m);
136   for i:=1 to m do
137   begin
138     readln(x,y,z);
139     add(x,y,z);
140   end;
141   dij;
142   writeln(d[t]);
143 end.

View Code