1726: [Usaco2006 Nov]Roadblocks第二短路

  1 type
  2     point=^node;
  3     node=record
  4                g,w:longint;
  5                next:point;
  6     end;
  7     arr=array[0..20000] of longint;
  8 var
  9    i,j,k,l,m,n:longint;
 10    a:array[0..20000] of point;
 11    b,c,d:arr;
 12    e:array[0..200000,1..3] of longint;
 13 procedure add(x,y,z:longint);inline;
 14           var p:point;
 15           begin
 16                new(p);
 17                p^.g:=y;
 18                p^.w:=z;
 19                p^.next:=a[x];
 20                a[x]:=p;
 21           end;
 22 procedure doit(x:longint;var b,c:arr);
 23           var
 24              i,j,k,l:longint;
 25              p:point;
 26           begin
 27                fillchar(b,sizeof(b),0);
 28                fillchar(c,sizeof(c),0);
 29                c[x]:=1;
 30                p:=a[x];
 31                while p<>nil do
 32                      begin
 33                           b[p^.g]:=p^.w;
 34                           p:=p^.next;
 35                      end;
 36                for i:=1 to n-1 do
 37                    begin
 38                         k:=maxlongint;
 39                         l:=-1;
 40                         for j:=1 to n do
 41                             begin
 42                                  if (c[j]=0) and (b[j]<>0) then
 43                                     begin
 44                                          if b[j]<k then
 45                                             begin
 46                                                  k:=b[j];
 47                                                  l:=j;
 48                                             end;
 49                                     end;
 50                             end;
 51                         c[l]:=1;
 52                         if l=-1 then break;
 53                         p:=a[l];
 54                         while p<>nil do
 55                               begin
 56                                    if c[p^.g]=0 then
 57                                       if (b[p^.g]=0) or (b[p^.g]>(k+p^.w)) then b[p^.g]:=k+p^.w;
 58                                    p:=p^.next;
 59                               end;
 60                    end;
 61                for i:=1 to n do
 62                    if (c[i]=0) and (i<>x) then b[i]:=maxlongint;
 63           end;
 64 
 65 begin
 66      readln(n,m);
 67      for i:=1 to n do a[i]:=nil;
 68      for i:=1 to m do
 69          begin
 70               readln(e[i,1],e[i,2],e[i,3]);
 71               add(e[i,1],e[i,2],e[i,3]);
 72               add(e[i,2],e[i,1],e[i,3]);
 73          end;
 74      doit(1,b,c);
 75      doit(n,c,d);
 76      l:=b[n];k:=maxlongint;
 77      for i:=1 to m do
 78          begin
 79               if (b[e[i,1]]<maxlongint) and (c[e[i,2]]<maxlongint) then
 80                  begin
 81                       j:=b[e[i,1]]+c[e[i,2]]+e[i,3];
 82                       if j<l then
 83                          begin
 84                               k:=l;l:=j;
 85                          end
 86                       else
 87                           if (j>l) and (j<k) then k:=j;
 88                  end;
 89               if (b[e[i,2]]<maxlongint) and (c[e[i,1]]<maxlongint) then
 90                  begin
 91                       j:=b[e[i,2]]+c[e[i,1]]+e[i,3];
 92                       if j<l then
 93                          begin
 94                               k:=l;l:=j;
 95                          end
 96                       else
 97                           if (j>l) and (j<k) then k:=j;
 98                  end;
 99          end;
100      writeln(k);
101      readln;
102 
103 end.
104