全点対間最短経路(ワーシャルフロイド法)

問題

実行時間制限: 1 sec/ メモリ制限: 65536 KB
重み付き有向グラフ \(G=(V,E)\) の全点対間最短経路の距離を列挙してください。

入力

  • 入力は以下の形式で与えられる。
\(|V| \hspace{8px} |E|\)
\(s_0 \hspace{8px} t_0 \hspace{8px} d_0 \)
\(s_1 \hspace{8px} t_1 \hspace{8px} d_1 \)
:
\(s_{|E|-1} \hspace{8px} t_{|E|-1} \hspace{8px} d_{|E|-1} \)
  • \(|V|,|E|\) はそれぞれグラフ \(G\) の頂点の数と辺の数を示す。グラフ \(G\) の頂点はそれぞれ \(0,1,...,|V|-1\) の番号が付されている。
  • \(s_i,t_i,d_i\) はグラフの \(G\) の \(i\) 番目の辺が結ぶ(有向) \(2\) つの頂点の番号とその重みを表す。

出力

  • グラフ \(G\) が負の閉路(辺の重みの和が負になるような閉路)を持つ場合は以下の1行を出力せよ。
\(NEGATIVE \hspace{8px} CYCLE\)
  • それ以外の場合は、以下の形式で距離を出力せよ。
\(D_{0,0} \hspace{8px} D_{0,1} \hspace{8px} ... \hspace{8px} D_{0,|v|-1} \)
\(D_{1,0} \hspace{8px} D_{1,1} \hspace{8px} ... \hspace{8px} D_{1,|v|-1} \)
:
\(D_{|v|-1,0} \hspace{8px} D_{|v|-1,1} \hspace{8px} ... \hspace{8px} D_{|v|-1,|v|-1} \)
  • 出力は \(|V|\) 行からなる。 \(i\) 行目に頂点 \(i\) から各頂点 \(j\) への最短経路の距離を順番に出力せよ。 \(i\) から \(j\) への経路がない場合は \(INF\)と出力せよ。距離の間に \(1\) つの空白を出力せよ。

制約

  • \(1 \leqq |V| \leqq 100\)
  • \(0 \leqq |E| \leqq 9900\)
  • \(-2 × 10^7 \leqq d_i \leqq 2 × 10^7\)
  • グラフ \(G\) に多重辺はない。
  • グラフ \(G\) に自己ループはない。

例1

入力

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

出力

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

例2

入力

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

出力

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

例3

入力

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

出力

\(NEGATIVE \hspace{8px} CYCLE\)

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

解答例(C++)

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

int main() {

  // 大きい値を用意する
  long long INF = 1LL<<60;

  // V は頂点数
  long long V, E;
  cin >> V >> E;

  // 要素数はN + 1
  // あらかじめ INF を入れておく
  long long g[101][101];
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      if (i != j) {
        g[i][j] = INF;
      } else {
        g[i][j] = 0;
      }
    }
  }

  // 頂点 s から頂点 t までの重みが d
  int s, t;
  long long d;
  for (int i = 0; i < E; i++) {
    cin >> s >> t >> d;
    g[s][t] = d;
  }

  // ワーシャルフロイドで全点間の距離を計算する
  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      if (g[i][k] == INF) {
        continue;
      }
      for (int j = 0; j < V; j++) {
        if (g[k][j] == INF) {
          continue;
        }
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }

  // 出力
  bool flg = false;
  for (int i = 0; i < V; i++) {
    if (g[i][i] < 0) {
      flg = true;
    }
  }

  if (flg) {
    cout << "NEGATIVE CYCLE" << endl;
  } else {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        if (g[i][j] == INF) {
          cout << "INF";
        } else {
          cout << g[i][j];
        }
        if (j != V - 1) {
          cout << " ";
        }
      }
      cout << endl;
    }
  }

  return 0;
}