forked from stevenhalim/cpbook-code
-
Notifications
You must be signed in to change notification settings - Fork 0
/
floyd_warshall.cpp
48 lines (39 loc) · 1.03 KB
/
floyd_warshall.cpp
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
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9; // INF = 1B, not 2^31-1 to avoid overflow
const int MAX_V = 450; // if |V| > 450, you cannot use Floyd Washall's
int AM[MAX_V][MAX_V]; // it is better to store a big array in the heap
int main() {
/*
// Graph in Figure 4.30
5 9
0 1 2
0 2 1
0 4 3
1 3 4
2 1 1
2 4 1
3 0 1
3 2 3
3 4 5
*/
freopen("floyd_warshall_in.txt", "r", stdin);
int V, E; scanf("%d %d", &V, &E);
for (int u = 0; u < V; ++u) {
for (int v = 0; v < V; ++v)
AM[u][v] = INF;
AM[u][u] = 0;
}
for (int i = 0; i < E; ++i) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
AM[u][v] = w; // directed graph
}
for (int k = 0; k < V; ++k) // loop order is k->u->v
for (int u = 0; u < V; ++u)
for (int v = 0; v < V; ++v)
AM[u][v] = min(AM[u][v], AM[u][k]+AM[k][v]);
for (int u = 0; u < V; ++u)
for (int v = 0; v < V; ++v)
printf("APSP(%d, %d) = %d\n", u, v, AM[u][v]);
return 0;
}