| 1 | int* bellman_ford(int n, int s, vii* adj, bool& ncycle) { |
| 2 | ncycle = false; |
| 3 | int* dist = new int[n]; |
| 4 | rep(i,0,n) dist[i] = i == s ? 0 : INF; |
| 5 | rep(i,0,n-1) rep(j,0,n) if (dist[j] != INF) |
| 6 | rep(k,0,size(adj[j])) |
| 7 | dist[adj[j][k].first] = min(dist[adj[j][k].first], |
| 8 | dist[j] + adj[j][k].second); |
| 9 | rep(j,0,n) rep(k,0,size(adj[j])) |
| 10 | if (dist[j] + adj[j][k].second < dist[adj[j][k].first]) |
| 11 | ncycle = true; |
| 12 | return dist; } |
| 13 | // vim: cc=60 ts=2 sts=2 sw=2: |