Roadblocks

問題

実行時間制限: - / メモリ制限: -
\(R\) 本の道と \(N\) 個の交差点がある街がある。道路は両方向に通行可能である。\(1\) 番目の交差点から \(N\) 番の交差点への \(2\) 番目の最短路の長さを求めよ。ただし、\(2\) 番目の最短路とは、最短路よりも真に長いもののうちで最短のもののことをいう。同じ道路を複数回通ってもかまわない。

入力

  • 最初の行に交差点の数 \(N\) と道の数 \(R\) が与えられる。続く \(R\) 行で各交差点 \(u\) の隣接リストが以下の形式で与えられる。
\(u \hspace{8px} k \hspace{8px} v_1 \hspace{8px} c_1 \hspace{8px} v_2 \hspace{8px} c_2 ... \hspace{8px} v_k \hspace{8px} c_k\)

\(N\) の各交差点 \(1\) から \(N\) の番号が付されている。 \(u\) は交差点の番号であり、 \(k\) は \(u\) の出次数を示す。 \(v_i(i=1,2,...,k)\) は \(u\) に隣接する交差点の番号であり、 \(c_i\) は \(u\) と \(v_i\) をつなぐ無向辺の重みを示す。

出力

  • \(2\) 番目の最短路の長さを出力せよ。

制約

  • \(1 \leqq N \leqq 5000\)
  • \(0 \leqq R \leqq 100000\)

例1

入力

\(4 \hspace{8px} 4\)
\(1 \hspace{8px} 1 \hspace{8px} 2 \hspace{8px} 100\)
\(2 \hspace{8px} 3 \hspace{8px} 1 \hspace{8px} 100 \hspace{8px} 3 \hspace{8px} 250 \hspace{8px} 4 \hspace{8px} 200\)
\(3 \hspace{8px} 2 \hspace{8px} 2 \hspace{8px} 250 \hspace{8px} 4 \hspace{8px} 100\)
\(4 \hspace{8px} 2 \hspace{8px} 2 \hspace{8px} 200 \hspace{8px} 3 \hspace{8px} 100\)

出力

\(450\)

【出典・参考】
秋葉拓哉 , 岩田陽一他「プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~」 102〜103頁

解答例(C++)

#include <bits/stdc++.h>
using namespace std;

// 頂点fromから頂点toへの重みcost
struct edge {
  int from, to, cost;
};

int INF;
int n, r;

vector<edge> g[101];

// sから各頂点への最短経路を求める
void dijkstra () {

  // first:最短距離 second:頂点の番号
  // 小さい順で管理する
  priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

  // 最短路
  int d[101];

  // 2番目の最短路
  int d2[101];

  // 初期化
  for (int i = 0; i < n; i++) {
    d[i] = INF;
    d2[i] = INF;
  }

  d[0] = 0;
  pq.push(make_pair(0,0));

  while (!pq.empty()) {

    // 距離が小さいものを取り出す
    pair<int, int> p = pq.top(); pq.pop();
    // その頂点
    int v = p.second;
    // 距離
    int d_ = p.first;

    // 2番目の最短距離より距離が大きい場合は次へ
    if (d2[v] < d_) {
      continue;
    }

    // その頂点から出ている辺の数だけ繰り返す
    for (int i = 0; i < g[v].size(); i++) {

      // 辺を取り出す
      edge e = g[v][i];

      // 更新後の距離 = それまでの距離 + 追加する距離
      int d2_ = d_ + e.cost;

      // 更新後の距離が最短路より小さい場合は
      if (d2_ < d[e.to]) {
        // 最短路と入れ替える。
        swap(d[e.to], d2_);
        // 入れ替えた内容をキューに追加しておく
        pq.push(make_pair(d[e.to], e.to));
      }

      // 更新後の距離が2番目の最短路の場合は
      if (d2_ < d2[e.to] && d[e.to] < d2_) {
        // 2番目の最短路を入れ替える
        d2[e.to] = d2_;
        // キューに追加
        pq.push(make_pair(d2[e.to], e.to));
      }
    }

  }

  // 答えを出力
  cout << d2[n - 1] << endl;

}

int main() {

  cin >> n >> r;

  INF = 20000000;

  // 入力を受け取る
  for (int i = 0; i < r; i++) {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; j++) {
      int v, c;
      cin >> v >> c;
      edge e = {u - 1, v - 1, c};
      g[u - 1].push_back(e);
    }
  }

  // ダイクストラ法開始
  dijkstra();

  return 0;
}

ダイクストラ法の応用

ダイクストラ法は未確定な頂点の中で距離が最小のものを順に確定させていくアルゴリズムなので、これを修正する。

ある頂点 \(v\) への \(2\) 番目の最短路は、
・他の頂点 \(u\) への最短路に \(u→v\) をつなげたもの
・\(u\) への \(2\) 番目の最短路に \(u→v\) をつなげたもの
のどちらかである。必要なのは全頂点への最短路および \(2\) 番目の最短路であり、この \(2\) つの距離を更新していく。