1726: [Usaco2006 Nov]Roadblocks第二短路

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 835 Solved: 398
[Submit][Status]

Description

贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。

Input

* 第1行: 两个整数，N和R，用空格隔开

* 第2..R+1行: 每行包含三个用空格隔开的整数A、B和D，表示存在一条长度为 D(1 <= D <= 5000)的路连接农场A和农场B

Output

* 第1行: 输出一个整数，即从农场1到农场N的第二短路的长度

Sample Input

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

输出说明:

最短路：1 -> 2 -> 4 (长度为100+200=300)
第二短路：1 -> 2 -> 3 -> 4 (长度为100+250+100=450)

HINT

Source

Gold

题解：经典的严格第二短路径问题，其实原理也不难，就是先从1开始来一遍dijkstra，再反着来一遍，然后设1-X最短路径为B[x]，x-n最短路径为C[x]，则在dis[i,j]+b[i]+c[j]中找出严格次小的即可（由于是严格次小，所以注意判重）

 type

     point=^node;

     node=record

                g,w:longint;

                next:point;

     end;

     arr=array[..] of longint;

 var

    i,j,k,l,m,n:longint;

    a:array[..] of point;

    b,c,d:arr;

    e:array[..,..] of longint;

 procedure add(x,y,z:longint);inline;

           var p:point;

           begin

                new(p);

                p^.g:=y;

                p^.w:=z;

                p^.next:=a[x];

                a[x]:=p;

           end;

 procedure doit(x:longint;var b,c:arr);

           var

              i,j,k,l:longint;

              p:point;

           begin

                fillchar(b,sizeof(b),);

                fillchar(c,sizeof(c),);

                c[x]:=;

                p:=a[x];

                while p<>nil do

                      begin

                           b[p^.g]:=p^.w;

                           p:=p^.next;

                      end;

                for i:= to n- do

                    begin

                         k:=maxlongint;

                         l:=-;

                         for j:= to n do

                             begin

                                  if (c[j]=) and (b[j]<>) then

                                     begin

                                          if b[j]<k then

                                             begin

                                                  k:=b[j];

                                                  l:=j;

                                             end;

                                     end;

                             end;

                         c[l]:=;

                         if l=- then break;

                         p:=a[l];

                         while p<>nil do

                               begin

                                    if c[p^.g]= then

                                       if (b[p^.g]=) or (b[p^.g]>(k+p^.w)) then b[p^.g]:=k+p^.w;

                                    p:=p^.next;

                               end;

                    end;

                for i:= to n do

                    if (c[i]=) and (i<>x) then b[i]:=maxlongint;

           end;

 begin

      readln(n,m);

      for i:= to n do a[i]:=nil;

      for i:= to m do

          begin

               readln(e[i,],e[i,],e[i,]);

               add(e[i,],e[i,],e[i,]);

               add(e[i,],e[i,],e[i,]);

          end;

      doit(,b,c);

      doit(n,c,d);

      l:=b[n];k:=maxlongint;

      for i:= to m do

          begin

               if (b[e[i,]]<maxlongint) and (c[e[i,]]<maxlongint) then

                  begin

                       j:=b[e[i,]]+c[e[i,]]+e[i,];

                       if j<l then

                          begin

                               k:=l;l:=j;

                          end

                       else

                           if (j>l) and (j<k) then k:=j;

                  end;

               if (b[e[i,]]<maxlongint) and (c[e[i,]]<maxlongint) then

                  begin

                       j:=b[e[i,]]+c[e[i,]]+e[i,];

                       if j<l then

                          begin

                               k:=l;l:=j;

                          end

                       else

                           if (j>l) and (j<k) then k:=j;

                  end;

          end;

      writeln(k);

      readln;

 end.

1726: [Usaco2006 Nov]Roadblocks第二短路