3255 -- Roadblocks

http://acm.pku.edu.cn/JudgeOnline/problem?id=3255
重み付きグラフが与えられて，2番目にコストが小さい経路のコストを出力する問題．

1番コストが小さいものなら普通のダイクストラ法でいいのだが，今回は2番目なので各頂点に対して2番目までのコストを覚えておいて更新するようにして解いた．

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

template <typename T>
T dijkstra(const vector<vector<pair<int,T> > >& g, int start, int goal)
{
  const int N = g.size();
  vector<T> costs1(N, numeric_limits<T>::max()), costs2(N, numeric_limits<T>::max());
  priority_queue<pair<T,int> > q;
  q.push(make_pair(0, start));
  while (!q.empty()) {
    const T cost = -q.top().first;
    const int node = q.top().second;
    q.pop();
    if (costs2[node] <= cost) {
      continue;
    }
    if (costs1[node] > cost) {
      costs1[node] = cost;
    } else {
      costs2[node] = cost;
    }

    for (typename vector<pair<int,T> >::const_iterator it(g[node].begin()); it != g[node].end(); ++it) {
      q.push(make_pair(-(cost + it->second), it->first));
    }
  }
  return costs2[goal];
}

int main()
{
  int N, R;
  cin >> N >> R;
  vector<vector<pair<int,int> > > g(N);
  for (int i = 0; i < R; i++) {
    int a, b, d;
    cin >> a >> b >> d;
    g[a-1].push_back(make_pair(b-1, d));
    g[b-1].push_back(make_pair(a-1, d));
  }
  cout << dijkstra(g, 0, N-1) << endl;
  return 0;
}