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);
}