Roadblocks - poj3255 - 次短路+dijkstra

Roadblocks

Time Limit: 2000MS	Memory Limit: 65536K
Total Submissions: 19197	Accepted: 6749

Description

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

Input

Line 1: Two space-separated integers: N and R 

Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

Output

Line 1: The length of the second shortest path between node 1 and node N

Sample Input

4 4
1 2 100
2 4 200
2 3 250
3 4 100      

Sample Output

450      

Hint

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

Source

USACO 2006 November Gold

思路：

次短路问题，有两种解法，

第一种：另dist1记录最短路，dist2记录次短路

是在求最短路时，用一个变量d2记录长度大于最短路的距离，如果，dist2[e.to]>d2&&dist[e,to]<d2

就把d2的值赋给dist2

第二种：是以1为起点，走一趟dijkstra，求出各个点到起点的最短路，再以n为起点走一趟，求出各个点到终点的最短路，（这个图是双向的），然后再走一趟for循环。

int ans=INF; 
for(int i=0;i<k;i++){//k是边数 
	int tmp=d1[edge[i].from]+d2[edge[i].to]+edge[i].cost;
	if(tmp>d1[n]){
		ans=min(ans,tmp);//这种方法也可求第x短路 
	}
}
           

代码如下：

方法一：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring> 
#include<queue>

using namespace std;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const int maxn=5005;
struct edge{
	int to,cost;
	edge(int to,int cost):to(to),cost(cost){}
};
vector<edge> G[maxn];
int dist[maxn],dist2[maxn];
int n,r;

void dijkstra(){
	fill(dist,dist+n+1,INF);
	fill(dist2,dist2+n+1,INF);
	dist[1]=0;
	priority_queue<P,vector<P>,greater<P> >que;
	que.push(P(0,1));
	while(!que.empty()) {
		P p=que.top();que.pop();
		int v=p.second,d=p.first;
		if(dist2[v]<d)continue;
		for(int i=0;i<G[v].size();i++){
			edge &e=G[v][i];
			int d2=d+e.cost;
			if(d2<dist[e.to]){
				swap(d2,dist[e.to]);
				que.push(P(dist[e.to],e.to));
			}
			if(dist2[e.to]>d2&&d2>dist[e.to]){
				dist2[e.to]=d2;
				que.push(P(dist2[e.to],e.to));
			}
		} 
	}
	printf("%d\n",dist2[n]);
}

int main(){
	int a,b,d;
	scanf("%d%d",&n,&r);
	for(int i=1;i<=r;i++){
		scanf("%d%d%d",&a,&b,&d);
		G[a].push_back(edge(b,d));
		G[b].push_back(edge(a,d));
	}
	dijkstra();
}
           

第二种：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring> 
#include<queue>

using namespace std;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const int maxn=5005;
struct edge{
	int to,cost;
	edge(int to,int cost):to(to),cost(cost){}
};
struct edge1{
	int from,to,cost;
}en[200005];
vector<edge> G[maxn];
int dist1[maxn],dist2[maxn];
int n,r;

void dijkstra(int s,int dist[]){
	fill(dist,dist+n+1,INF);
	dist[s]=0;
	priority_queue<P,vector<P>,greater<P> >que;
	que.push(P(0,s));
	while(!que.empty()) {
		P p=que.top();que.pop();
		int v=p.second,d=p.first;
		for(int i=0;i<G[v].size();i++){
			edge &e=G[v][i];
			int d2=d+e.cost;
			if(d2<dist[e.to]){
				dist[e.to]=d2;
				que.push(P(dist[e.to],e.to));
			}
		} 
	}
}

int main(){
	int a,b,d,k=0;
	scanf("%d%d",&n,&r);
	for(int i=1;i<=r;i++){
		scanf("%d%d%d",&a,&b,&d);
		G[a].push_back(edge(b,d));
		G[b].push_back(edge(a,d));
		en[k].from=a;en[k].to=b;en[k++].cost=d;
		en[k].from=b;en[k].to=a;en[k++].cost=d;
	}
	dijkstra(1,dist1);
	dijkstra(n,dist2);
	int ans=INF;
	for(int i=0;i<k;i++){
		int tmp=dist1[en[i].from]+dist2[en[i].to]+en[i].cost;
		if(tmp>dist1[n]){
			ans=min(tmp,ans);
		}
	}
	printf("%d\n",ans);
}