首页 > 代码库 > 1726: [Usaco2006 Nov]Roadblocks第二短路
1726: [Usaco2006 Nov]Roadblocks第二短路
1726: [Usaco2006 Nov]Roadblocks第二短路
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 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
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)
输出说明:
最短路：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]中找出严格次小的即可（由于是严格次小，所以注意判重）
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
1726: [Usaco2006 Nov]Roadblocks第二短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。