贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
* 第1行: 两个整数，N和R，用空格隔开
* 第2..R+1行: 每行包含三个用空格隔开的整数A、B和D，表示存在一条长度为 D(1 <= D <= 5000)的路连接农场A和农场B
* 第1行: 输出一个整数，即从农场1到农场N的第二短路的长度
k短路..$A*$!
然而我这种不会$A*$的蒟蒻瑟瑟发抖，注意到k很小，所以其实可以跑分层图
在最短路可以更新的时候，把目前的最短路丢给第二短路然后更新
如果不行就看看能不能更新第二段路（注意要判断最短路严格小于目前更新的路程）
最后看看如果上面两步都没法更新能不能用次短路来更新次短路（在目前更新的路径等于最短路时就需要用到这一步）
然后就ok了，当然也可以跑两遍，然后枚举每条边找第二段路
#include <bits/stdc++.h> using namespace std ; #define N 200010 #define inf 0x3f3f3f3f int n , m ; int d[ N ][ 2 ] , vis[ N ] , q[ N ] ; // 0最短路 ， 1次短路 int head[ N ] , cnt ; struct node { int to , nxt , v ; } e[ N ] ; void ins( int u , int v , int w ) { e[ ++ cnt ].to = v ; e[ cnt ].nxt = head[ u ] ; e[ cnt ].v = w ; head[ u ] = cnt ; } void spfa() { int l = 1 , r = 2 ; for( int i = 1 ; i <= n ; i ++ ) d[ i ][ 0 ] = d[ 1 ][ 1 ] = inf ; q[ l ] = 1 ; vis[ 1 ] = 1 ; d[ 1 ][ 0 ] = 0 ; while( l != r ) { int u = q[ l ++ ] ; if( l == 200000 ) l = 1 ; vis[ u ] = 0 ; for( int i = head[ u ] ; i ; i = e[ i ].nxt ) { int v = e[ i ].to ; if( d[ v ][ 0 ] > d[ u ][ 0 ] + e[ i ].v ) { d[ v ][ 1 ] = d[ v ][ 0 ] ; d[ v ][ 0 ] = d[ u ][ 0 ] + e[ i ].v ; if( !vis[ v ] ) { vis[ v ] = 1 , q[ r ++ ] = v ; if( r == 200000 ) r = 1 ; } } if( d[ v ][ 0 ] < d[ u ][ 0 ] + e[ i ].v && d[ v ][ 1 ] > d[ u ][ 0 ] + e[ i ].v ) { //严格次短路，所以要判第一个条件 d[ v ][ 1 ] = d[ u ][ 0 ] + e[ i ].v ; if( !vis[ v ] ) { vis[ v ] = 1 , q[ r ++ ] = v ; if( r == 200000 ) r = 1 ; } } if( d[ v ][ 1 ] > d[ u ][ 1 ] + e[ i ].v ) { d[ v ][ 1 ] = d[ u ][ 1 ] + e[ i ].v ; if( !vis[ v ] ) { vis[ v ] = 1 , q[ r ++ ] = v ; if( r == 200000 ) r = 1 ; } } } } } int main() { scanf( "%d%d" , &n , &m ) ; for( int i = 1 , u , v , w ; i <= m ; i ++ ) { scanf( "%d%d%d" , &u , &v , &w ) ; ins( u , v , w ) ; ins( v , u , w ) ; } spfa() ; printf( "%d\n" , d[ n ][ 1 ] ) ; }
BZOJ1726: [Usaco2006 Nov]Roadblocks第二短路 K短路
原文：https://www.cnblogs.com/henry-1202/p/BZOJ1726.html