凡是差分约束系统的题目

都是转化为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+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 do107     begin108       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 do121       begin122         y:=p^.po;123         if d[y]>p^.len+mid then124         begin125           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 begin135   readln(t,m);136   for i:=1 to m do137   begin138     readln(x,y,z);139     add(x,y,z);140   end;141   dij;142   writeln(d[t]);143 end.