単一始点最短経路(ベルマンフォード法)

問題

実行時間制限: 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;

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

int INF;

// 各頂点に応じてedgeを入れておく
vector<vector<edge>> es;

// 最短距離
vector<int> dist;

// sから各頂点への最短経路を求める
bool bellmanFord (int n, int s) {
  dist[s] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < es[j].size(); k++) {
        edge e_ = es[j][k];
        if (dist[e_.from] != INF && dist[e_.to] > dist[e_.from] + e_.cost) {
          dist[e_.to] = dist[e_.from] + e_.cost;
          // n回目にも更新があるなら、負の閉路が存在する
          if (i == n - 1) {
            return true;
          }
        }
      }
    }
  }
  return false;
}

int main() {

  int n;
  cin >> n;

  INF = 2000000;

  // edgeは n × k 個入る
  es.resize(n);

  // 最短距離は n 個分使う
  dist = vector<int>(n, INF);

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

  // ベルマンフォード法開始(trueだと負の閉路がある)
  bool flg = bellmanFord(n, 0);

  // 最短距離を出力
  for (int i = 0; i < n; i++) {
    cout << i << " " <<  dist[i] << endl;
  }

  return 0;
}