grl_1_c all pairs shortest paths

GRL_1_C All Pairs Shortest Paths

GRL_1_C All Pairs Shortest Paths
Feb. 2, 2020, 1:52 p.m.

目次

解説

負の重みあり有効グラフのすべての頂点間の距離を求める問題.
負の重みがなければSingle source shortest pathsで使用したダイクストラで解ける.
負の重みがあればベルマンフォードで解けるが、$O(V^2E)$なので$O(V^3)$のフロイドワーシャルのほうが速い.

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#define MAX_N 101
#define MAX_E 9901
#define W_INF (1L << 32)

Int dist[MAX_N][MAX_N];
bool negative = false;

void apsp(Int n) {
  loop(k,0,n) {
    loop(u,0,n) {
      if (dist[u][k] == W_INF) continue;
      loop(v,0,n) {
        if (dist[k][v] == W_INF) continue;
        dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
      }

      if (dist[u][u] < 0) {
        negative = true;
        return;
      }
    }
  }
}


int main(void) {
  Int n, e, v, u, w;
  cin >> n >> e;
  loop(i,0,n) {
    loop(j,0,n) {
      dist[i][j] = (i == j) ? 0 : W_INF;
    }
  }

  loop(i,0,e) {
    cin >> u >> v >> w;
    dist[u][v] = w;
  }

  apsp(n);
  if (negative) cout << "NEGATIVE CYCLE" << endl;
  else {
    loop(u,0,n) {
      loop(v,0,n) {
        if (dist[u][v] == W_INF) cout << "INF";
        else cout << dist[u][v];
        if (v != n-1) cout << ' ';
      }
      cout << endl;
    }
  }
}