![BZOJ 1726: [Usaco2006 Nov]Roadblocks第二短路( 最短路 )](/default/index/img?u=aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhBdmFXMWhaMlZ6TUM1amJtSnNiMmR6TG1OdmJTOWliRzluTWpBeE5TODNNak00T1RZdk1qQXhOVEEyTHpBM01UWXdPRE16T0RNeU5ERXhOaTV3Ym1jPS5qcGc= "BZOJ 1726: [Usaco2006 Nov]Roadblocks第二短路( 最短路 )")
从起点和终点各跑一次最短路 , 然后枚举每一条边 , 更新answer
-----------------------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define rep( i , n ) for( int i = 0 ; i < n ; i++ )
#define clr( x , c ) memset( x , c , sizeof( x ) )
#define Rep( i , n ) for( int i = 1 ; i <= n ; ++i )
using namespace std;
const int maxn = 5000 + 5;
const int maxm = int( 1e5 ) + 5;
const int inf = 0x3f3f3f3f;
struct edge {
int to , dist;
edge* next;
};
edge* head[ maxn ];
edge* pt;
edge EDGE[maxm << 1 ];
void init() {
pt = EDGE;
clr( head , 0 );
}
void add( int u , int v , int d ) {
pt -> to = v;
pt -> dist = d;
pt -> next = head[ u ];
head[ u ] = pt++;
}
#define add_edge( u , v , d ) add( u , v , d ) , add( v , u , d )
struct Node {
int x , d;
bool operator < ( const Node &o ) const {
return d > o.d;
}
};
priority_queue< Node > Q;
int d[ 2 ][ maxn ];
int cur = 0;
void dijkstra( int S ) {
clr( d[ cur ] , inf );
d[ cur ][ S ] = 0;
Q.push( ( Node ) { S , 0 } );
while( ! Q.empty() ) {
Node o = Q.top();
Q.pop();
int x = o.x , dist = o.d;
if( d[ cur ][ x ] != dist )
continue;
for( edge* e = head[ x ] ; e ; e = e -> next ) {
int to = e -> to;
if( d[ cur ][ to ] > dist + e -> dist ) {
d[ cur ][ to ] = dist + e -> dist;
Q.push( ( Node ) { to , d[ cur ][ to ] } );
}
}
}
}
int main() {
// freopen( "test.in" , "r" , stdin );
init();
int n , m;
cin >> n >> m;
while( m-- ) {
int u , v , d;
scanf( "%d%d%d" , &u , &v , &d );
u-- , v--;
add_edge( u , v , d );
}
dijkstra( 0 );
cur ^= 1;
dijkstra( n - 1 );
int MIN = d[ cur ][ 0 ];
int ans = inf;
rep( i , n )
for( edge* e = head[ i ] ; e ; e = e -> next ) {
int dist = d[ 0 ][ i ] + d[ 1 ][ e -> to ] + e -> dist;
if( dist > MIN )
ans = min( dist , ans );
}
cout << ans << "\n";
return 0;
}
-----------------------------------------------------------------------------------------------------
1726: [Usaco2006 Nov]Roadblocks第二短路
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 861 Solved: 414
[Submit][Status][Discuss]
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
Sample Output
450
输出说明:
最短路：1 -> 2 -> 4 (长度为100+200=300)
第二短路：1 -> 2 -> 3 -> 4 (长度为100+250+100=450)
HINT
Source