POJ 1201 （差分约束）

1176 加权版

……还是差分约束

Program P1201;
var
   n,i,j,minq,maxq:longint;
   d:array[-1..60000] of longint;
   w:array[1..60000,1..3] of longint;
   flag:boolean;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure relax(v,u,w:longint);
begin
   if (d[u]+w<d[v]) then
   begin
      d[v]:=d[u]+w;
      flag:=false;
   end;
end;
procedure bellman_ford;
var
   i,j,k:longint;
begin
   //d[w[i,2]] - d[w[i,1]-1]>=2 ->d[w[i,1]-1]-d[w[i,2]]<=-2
   //d[i]-d[i-1]<=1
   //d[i]-d[i-1]>=0 ->d[i-1]-d[i]<=0

   d[minq-1]:=0;
   while (true) do
   begin
      flag:=true;
//    for i:=minq to maxq do relax(i,minq-1,0);
      for i:=1 to n do relax(w[i,1]-1,w[i,2],-w[i,3]);
      for i:=minq to maxq do relax(i,i-1,1);
      for i:=maxq downto minq do relax(i-1,i,0);
      if flag then break;
   end;
end;
begin
   while not seekeof do
   begin
      minq:=maxlongint;  maxq:=0;
      fillchar(d,sizeof(d),0);
      read(n);
      for i:=1 to n do
      begin
         read(w[i,1],w[i,2],w[i,3]);
         minq:=min(minq,w[i,1]);
         maxq:=max(maxq,w[i,2]);
      end;
      bellman_ford;
      writeln(d[maxq]-d[minq-1]);
   end;
end.