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

問題

実行時間制限: 1 sec/ メモリ制限: 65536 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 100\)
  • \(0 \leqq c_i \leqq 100000\)
  • \(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, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 302〜308頁
AIZU ONLINE JUDGE ADLS1_12_B https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_B

解答例(C++)

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

int INF;
int n;
int es[100][100];

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

  int minv;
  int d[100];

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

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

  d[0] = 0;
  status[0] = 1;

  while (1) {
    minv = INF;
    int u = -1;
    for (int i = 0; i < n; i++) {
      if (d[i] < minv && status[i] != 2) {
        u = i;
        minv = d[i];
      }
    }
    if (u == -1) {
      break;
    }
    status[u] = 2;
    for (int v = 0; v < n; v++) {
      if (status[v] != 2 && es[u][v] != INF) {
        if (d[u] + es[u][v] < d[v]) {
          d[v] = d[u] + es[u][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 = 2000000;

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

  // 入力を受け取る
  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][v] = c;
    }
  }

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

  return 0;
}