POJ3255(次最短路)

描述

求1到n的次最短路

开个

d

i

s

[

m

a

x

n

]

2

dis[maxn][2]

dis[maxn][2]的储存距离的二维数组，0储存最短路，1储存次短路

初始化全为正无穷，

1

=

;

dis[1][0]=0;

然后遍历更新时，先尝试更新最短路和次短路，不行就尝试更新次短路;

如果入队的距离已经大于次短路的距离，那么没必要继续，continue;