POJ-3255: Roadblocks

keyword

Dijkstra　C++

問題概要

ノード数V(<5000)、エッジ数E(<10^5)の重み付き無向グラフが与えられる。ノード１からノードNへの経路のうち2番目に短いものを求める問題。

解法

Dijkstraするだけ。各ノードまでの最短距離のうち2番めに短いものまで覚えておけばよい。実装時間15分くらい。

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

struct edge{
	int to, cost;
};

const int MAX_V = 5009;
vector<edge> G[MAX_V];
vector<int> dist[MAX_V];
int V;

int solve(){
	priority_queue< pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q;
	Q.push( make_pair(0, 0) );
	while(!Q.empty()){
		pair<int,int> tp = Q.top(); Q.pop();
		int cur = tp.second, d = tp.first;
		if(dist[cur].size() == 2) continue;
		if(dist[cur].empty() || dist[cur][0] < d){
			dist[cur].push_back(d);
			if(cur==V-1 && dist[cur].size() == 2) return d;
			for(int i=0; i<(int)G[cur].size(); i++){
				edge e = G[cur][i];
				if(dist[e.to].size() < 2){
					Q.push( make_pair(d + e.cost, e.to) );
				}
			}
		}
		else{
			continue;
		}
	}
	return -1;
}

int main(){
	int R;
	scanf("%d%d",&V,&R);
	for(int i=0; i<R; i++){
		int x, y, d;
		scanf("%d%d%d", &x,&y,&d);
		x--; y--;
		G[x].push_back((edge){y, d});
		G[y].push_back((edge){x, d});
	}
	printf("%d\n",solve());
	return 0;
}