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.

## 解答

  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; } } }