[题目来源]：tyvj二月月赛
[关键字]：次短路径
[题目大意]：如果p=1则找出仅小于最短路径长度的路径长度，否则找出虽短路径。
//============================================================================================================
[分析]：因为是无向图所以就从1到n找一遍最短路记录1到每个点距离为d1[]，从n到1找一遍最短路记录n到每个点距离为d2[]。则此时仅次于最短路径长度的路径长度为：max(d1[x]+d2[t].t+e[t].d )且d1[x]+d2[e[t].y]+e[].d > d1[n]。
[代码]：
View Code 1 type
2 rec = record
3 y, n, d: longint;
4 end;
5 var
6 n, m, p, ans, tot: longint;
7 d1, d2: array[0..20000] of longint;
8 q: array[0..200000] of longint;
9 b: array[0..20000] of boolean;
10 e: array[0..200000] of rec;
11 link: array[0..20000] of longint;
12
13 procedure make(x, y, d: longint);
14 begin
15 inc(tot);
16 e[tot].y := y;
17 e[tot].d := d;
18 e[tot].n := link[x];
19 link[x] := tot;
20 end;
21
22 procedure init;
23 var
24 i, x, y, z: longint;
25 begin
26 readln(n,m);
27 tot := 0;
28 for i := 1 to m do
29 begin
30 //writeln(i);
31 readln(x,y,z);
32 make(x,y,z);
33 make(y,x,z);
34 end;
35 readln(p);
36 end;
37
38 procedure spfa2;
39 var
40 head, tail, t, x, y: longint;
41 begin
42 head := 1;
43 tail := 1;
44 q[1] := n;
45 fillchar(b,sizeof(b),false);
46 b[n] := true;
47 fillchar(d2,sizeof(d2),100);
48 d2[n] := 0;
49 while head <= tail do
50 begin
51 x := q[head];
52 t := link[x];
53 while t <> 0 do
54 begin
55 y := e[t].y;
56 if d2[y] > d2[x]+e[t].d then
57 begin
58 d2[y] := d2[x]+e[t].d;
59 if not b[y] then
60 begin
61 inc(tail);
62 q[tail] := y;
63 b[y] := true;
64 end;
65 end;
66 t := e[t].n;
67 end;
68 b[x] := false;
69 inc(head);
70 end;
71 end;
72
73 procedure spfa1;
74 var
75 head, tail, t, x, y: longint;
76 begin
77 head := 1;
78 tail := 1;
79 q[1] := 1;
80 fillchar(b,sizeof(b),false);
81 b[1] := true;
82 fillchar(d1,sizeof(d1),100);
83 d1[1] := 0;
84 while head <= tail do
85 begin
86 x := q[head];
87 t := link[x]; //binstr(10,31);
88 while t <> 0 do
89 begin
90 y := e[t].y;
91 if d1[y] > d1[x]+e[t].d then
92 begin
93 d1[y] := d1[x]+e[t].d;
94 if not b[y] then
95 begin
96 inc(tail);
97 q[tail] := y;
98 b[y] := true;
99 end;
100 end;
101 t := e[t].n;
102 end;
103 b[x] := false;
104 inc(head);
105 end;
106 end;
107
108 procedure work;
109 var
110 i, t, y: longint;
111 begin
112 if p = 0 then
113 begin
114 ans := d1[n];
115 exit;
116 end;
117 ans := maxlongint;
118 for i := 1 to n do
119 begin
120 t := link[i];
121 while t <> 0 do
122 begin
123 y := e[t].y;
124 if (d1[i]+d2[y]+e[t].d > d1[n]) and (ans > d1[i]+d2[y]+e[t].d) then ans := d1[i]+d2[y]+e[t].d;
125 t := e[t].n;
126 end;
127 end;
128 end;
129
130 begin
131 assign(input,'c:\1.in');reset(input);
132 assign(output,'c:\1.out');rewrite(output);
133 init;
134 spfa1;
135 if p = 1 then spfa2;
136 work;
137 writeln(ans);
138 close(input);
139 close(output);
140 end.
