POJ 3255: Roadblocks

問題
http://poj.org/problem?id=3255

概要
1番目の頂点からN番目の頂点への経路の内二番目に短いものの長さを求めよ。
（最短経路が二つ以上ある場合、その値を出力）

解法・感想
アリ本p102より。ダイクストラ法の改良。
最小の距離と二番目に小さい距離をdist,dist2に記憶するようダイクストラ法を進めればOKです。
ただし、既に通った/通っていないかでヒープに追加するかの判断はできません。
また、1->2->1->2のような経路がdist2となる場合もあるので注意が必要です。
アリ本ではdist2を更新するブロックで
if(dist2[e.to] > d2 && dist[e.to] < d2)
となっていますが、dist[e.to] < d2 は不要です

ソースコード

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#define INF (1 << 30)
#define MAX_N 5001
#define MAX_R 100001
#define DBG 0
using namespace std;
int N,R;
struct edge{int to, cost;};
typedef pair<int, int> P;
vector<edge> G[MAX_N];

int dist[MAX_N];
int dist2[MAX_N];

void solve(){
  priority_queue<P, vector<P>, greater<P> > pq;
  fill(dist, dist+N, INF);
  fill(dist2, dist2+N, INF);
  dist[0] = 0;
  pq.push(P(0, 0));
  while(!pq.empty()){
 P p = pq.top();
 if(DBG){
   cout << p.first << " " << p.second << endl;
 }
 pq.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(dist[e.to] > d2){
  swap(dist[e.to], d2);
  pq.push(P(dist[e.to], e.to));
   }
   if(dist2[e.to] > d2){
  dist2[e.to] = d2;
  pq.push(P(dist2[e.to], e.to));
   }
 }
  }
  cout << dist2[N-1] << endl;
}

int main(){
  cin >> N >> R;
  for(int i = 0; i < R; i++){
 int s,t,c;
 scanf("%d %d %d", &s, &t, &c);
 G[s-1].push_back((edge){t-1, c});
 G[t-1].push_back((edge){s-1, c});
  }
  solve();
  return 0;
}

こっちの方が個人的にはわかりやすい。

if(dist2[e.to] > d2){
    dist2[e.to] = d2;
    if(dist[e.to] > dist2[e.to]){
        swap(dist[e.to], dist2[e.to]);
        pq.push(P(dist[e.to], e.to));
    }
    else{
        pq.push(P(dist2[e.to], e.to));
    }
}