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)
Solution
k短路..$A*$!
然而我这种不会$A*$的蒟蒻瑟瑟发抖，注意到k很小，所以其实可以跑分层图
在最短路可以更新的时候，把目前的最短路丢给第二短路然后更新
如果不行就看看能不能更新第二段路（注意要判断最短路严格小于目前更新的路程）
最后看看如果上面两步都没法更新能不能用次短路来更新次短路（在目前更新的路径等于最短路时就需要用到这一步）
然后就ok了，当然也可以跑两遍，然后枚举每条边找第二段路
#include <bits/stdc++.h> using namespace std ; #define N 200010
#define inf 0x3f3f3f3f int n , m ;
int d[ N ][ ] , 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 = , r = ;
for( int i = ; i <= n ; i ++ ) d[ i ][ ] = d[ ][ ] = inf ;
q[ l ] = ; vis[ ] = ; d[ ][ ] = ;
while( l != r ) {
int u = q[ l ++ ] ;
if( l == ) l = ;
vis[ u ] = ;
for( int i = head[ u ] ; i ; i = e[ i ].nxt ) {
int v = e[ i ].to ;
if( d[ v ][ ] > d[ u ][ ] + e[ i ].v ) {
d[ v ][ ] = d[ v ][ ] ;
d[ v ][ ] = d[ u ][ ] + e[ i ].v ;
if( !vis[ v ] ) {
vis[ v ] = , q[ r ++ ] = v ;
if( r == ) r = ;
}
}
if( d[ v ][ ] < d[ u ][ ] + e[ i ].v && d[ v ][ ] > d[ u ][ ] + e[ i ].v ) {
//严格次短路，所以要判第一个条件
d[ v ][ ] = d[ u ][ ] + e[ i ].v ;
if( !vis[ v ] ) {
vis[ v ] = , q[ r ++ ] = v ;
if( r == ) r = ;
}
}
if( d[ v ][ ] > d[ u ][ ] + e[ i ].v ) {
d[ v ][ ] = d[ u ][ ] + e[ i ].v ;
if( !vis[ v ] ) {
vis[ v ] = , q[ r ++ ] = v ;
if( r == ) r = ;
}
}
}
}
} int main() {
scanf( "%d%d" , &n , &m ) ;
for( int i = , 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 ][ ] ) ;
}