単一始点最短経路(ダイクストラ法2)

問題

実行時間制限: 1 sec/ メモリ制限: 131072 KB
与えられた重み付きグラフ \(G=(V,E)\) について、単一始点最短距離のコストを求めるプログラムを作成せよ。 \(G\) の頂点を \(0\) を始点とし、 \(0\) から各頂点 \(v\) について、最短経路上の辺の重みの総和 \(d[v]\) を出力せよ。

入力

  • 最初の行に \(G\) の頂点数 \(n\) が与えられる。続く \(n\) 行で各頂点 \(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\)

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

出力

  • 各頂点の番号 \(v\) と距離 \(d[v]\) を \(1\) つの空白区切りで順番に出力せよ。

制約

  • \(1 \leqq n \leqq 100000\)
  • \(0 \leqq c_i \leqq 100000\)
  • \(|E| \leqq 500000\)
  • \(0\) から各頂点へは必ず経路が存在する。

例1

入力

\(5\)
\(0 \hspace{8px} 3 \hspace{8px} 2 \hspace{8px} 3 \hspace{8px} 3 \hspace{8px} 1 \hspace{8px} 1 \hspace{8px} 2\)
\(1 \hspace{8px} 2 \hspace{8px} 0 \hspace{8px} 2 \hspace{8px} 3 \hspace{8px} 4\)
\(2 \hspace{8px} 3 \hspace{8px} 0 \hspace{8px} 3 \hspace{8px} 3 \hspace{8px} 1 \hspace{8px} 4 \hspace{8px} 1\)
\(3 \hspace{8px} 4 \hspace{8px} 2 \hspace{8px} 1 \hspace{8px} 0 \hspace{8px} 1 \hspace{8px} 1 \hspace{8px} 4 \hspace{8px} 4 \hspace{8px} 3\)
\(4 \hspace{8px} 2 \hspace{8px} 2 \hspace{8px} 1 \hspace{8px} 3 \hspace{8px} 3\)

出力

\(0 \hspace{8px} 0\)
\(1 \hspace{8px} 2\)
\(2 \hspace{8px} 2\)
\(3 \hspace{8px} 1\)
\(4 \hspace{8px} 3\)

【出典・参考】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 309〜314頁
AIZU ONLINE JUDGE ADLS1_12_C https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_C

解答例(C++)

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

int INF;
int n;
vector<pair<int, int>> es[10000];

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

  priority_queue<pair<int, int>> pq;
  int d[10000];

  // 0:未調査 1:調査中 2:調査完了
  int status[10000];

  for (int i = 0; i < n; i++) {
    d[i] = INF;
    status[i] = 0;
  }

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

  while (!pq.empty()) {

    pair<int, int> p = pq.top(); pq.pop();
    int u = p.second;
    status[u] = 2;

    // 最小値を取り出し、それが最短でなければ無視
    if (d[u] < p.first * (-1)) {
      continue;
    }

    for (int i = 0; i < es[u].size(); i++) {
      int v = es[u][i].first;
      if (status[v] == 2) {
        continue;
      }
      if (d[u] + es[u][i].second < d[v]) {
        d[v] = d[u] + es[u][i].second;
        // priority_queueはデフォルトで大きい順を優先するため-1を掛ける
        pq.push(make_pair(d[v] * (-1), v));
        status[v] = 1;
      }
    }

  }
  for (int i = 0; i < n; i++) {
    if (d[i] == INF) {
      cout << i << " -1" << endl;
    } else {
      cout << i << " " << d[i] << endl;
    }
  }
}

int main() {

  cin >> n;

  INF = 20000000;

  // 入力を受け取る
  for (int i = 0; i < n; i++) {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; j++) {
      int v, c;
      cin >> v >> c;
      es[u].push_back(make_pair(v,c));
    }
  }

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

  return 0;
}