POJ_3255 Roadblocks
問題
グラフの頂点1からNまでの経路のうち、二番目に短いものの長さを求めよ。
解法
蟻本を参考にした。
ダイクストラ法を使って最短路と二番目の最短路を更新しながら計算していく。
#include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef pair<int, int> P; //距離、場所 const int MAX_N = 5000; const int INF = 1 << 30; class E{ public: int to, cost; E(int t, int c){ to = t; cost = c; } }; vector<E> g[MAX_N + 1]; int N, R; int dijk(){ priority_queue<P, vector<P>, greater<P> > Q; int d1[MAX_N + 1]; int d2[MAX_N + 1]; fill(d1, d1 + MAX_N + 1, INF); fill(d2, d2 + MAX_N + 1, INF); Q.push(P(0, 1)); while(!Q.empty()){ P p = Q.top(); Q.pop(); int d = p.first, pos = p.second; if(d >= d2[pos]) continue; if(d < d1[pos]){ d2[pos] = d1[pos]; d1[pos] = d; }else{ d2[pos] = d; } for(int i = 0; i < g[pos].size(); i++){ int c = g[pos][i].cost; int next_p = g[pos][i].to; if(d2[next_p] > d + c){ Q.push(P(d + c, next_p)); } } } return d2[N]; } int main(){ scanf("%d %d", &N, &R); for(int i = 0; i < R; i++){ int a, b, c; scanf("%d %d %d", &a, &b, &c); g[a].push_back(E(b, c)); g[b].push_back(E(a, c)); } printf("%d\n", dijk()); return 0; }