题目：Roadblocks

题目来源：POJ3255

分析

题目大意为：

给一个双向路径联通图，求节点1到节点N的第二短路(路程严格大于最短路)

解法

刚开始想到的是直接做最短路，用一个dist存最短路，用一个dist2存第二短路，即每次更新dist[i]时，把dist[i]的原有值给dist2[i]

但是发现这样很蛋疼。。

因为路程严格大于最短路，所以我们只要知道数值上大于最短路的就可以了，不必担心求出来的路径和最短路一样

（如最短路次短路都是10，求的时候就要保证他们不是来自同一路径）

这样的话我们可以两头做最短路

然后枚举边

找出除最短程以外的最短路程

优化

spfa + 边表

详解

1
ans = min (dist[1,i] + edg[i,j] + dist[j,n])  (ans>dist[1,n])

细节

存双向边，数组上线翻倍

spfa，数组上线再翻10-20倍

或者用循环队列

源程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
Program Lwx;
Var 	n, m:longint;
    	edg:array[1..200100, 1..4] of longint;
    	last, first:array[1..5005] of longint;
    	i, j, k, l, a, b, c, ans, top, fv:longint;
    	f:array[1..500100] of longint;
    	dist:array[1..2,1..5005] of longint;
    	past:array[1..5005] of boolean;

Begin
	//assign(input, 'test.in');reset(input);
  	readln(n, m);
	for i := 1 to m do
  	begin
		readln(a, b, c);
    		edg[i*2-1, 1] := a; edg[i*2-1, 2] := c; edg[i*2-1, 4] := b;
    		if first[b] = 0 then first[b] := i*2 - 1 else edg[last[b], 3] := i*2 - 1;
    		last[b] := i*2 - 1;
		edg[i*2, 1] := b; edg[i*2, 2] := c; edg[i*2, 4] := a;
    		if first[a] = 0 then first[a] := i*2 else edg[last[a], 3] := i*2;
    		last[a] := i*2;
  	end;

  	for a := 1 to 2 do
  	begin
    		fillchar(dist[a], sizeof(dist[a]), $ff);
    		fillchar(past, sizeof(past), true);
    		if a = 1 then
    		begin
      			f[1] := 1;
      			dist[a, 1] := 0;
      			past[1] := false;
    		end else
    		begin
      			f[1] := n;
      			dist[a, n] := 0;
      			past[n] := false;
    		end;
    		i := 0; j := 1;
    		while i < j do
    		begin
      			k := f[i+1];
      			l := first[k];
      			while l <> 0 do
      			begin
        			if (dist[a, edg[l, 1]] = -1)or(dist[a, k]+edg[l,2] < dist[a, edg[l, 1]]) then
        			begin
          				dist[a, edg[l, 1]] := dist[a, k] + edg[l, 2];
          				if past[edg[l, 1]] then
          				begin
            					inc(j);
            					f[j] := edg[l, 1];
            					past[edg[l, 1]] := false;
          				end;
        			end;
        			l := edg[l, 3];
      			end;
      			past[k] := true;
      			inc(i);
    		end;
  	end;
  	top := dist[1, n];
  	ans := maxlongint;
  	for i := 1 to 2*m do
 	begin
    		fv := edg[i, 2] + dist[1, edg[i, 4]] + dist[2, edg[i, 1]];
    		if (fv <> top)and(fv < ans) then ans := fv;
  	end;
  	write(ans);
  	//close(input);
End.