POJ-3255: Roadblocks
問題概要
ノード数V(<5000)、エッジ数E(<10^5)の重み付き無向グラフが与えられる。ノード1からノード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; }