| 1 | void floyd_warshall(int** arr, int n) { |
| 2 | rep(k,0,n) rep(i,0,n) rep(j,0,n) |
| 3 | if (arr[i][k] != INF && arr[k][j] != INF) |
| 4 | arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]); |
| 5 | // Check negative cycles |
| 6 | rep(i,0,n) rep(j,0,n) rep(k,0,n) |
| 7 | if (arr[i][k] != INF && arr[k][k] < 0 && arr[k][j]!=INF) |
| 8 | arr[i][j] = -INF; } |
| 9 | // vim: cc=60 ts=2 sts=2 sw=2: |