Cod sursa(job #900435)
#include <stdio.h>
#include <vector>
#define INF 0x3f3f3f3f
#define H 50010
using namespace std;
long n, m, aux, a[H], b[H], c[H], i, j, d[H], Q[H * 5], V[H];
vector < long > G[H], C[H];
int main() {
freopen("bellmanford.in", "r", stdin);
freopen("bellmanford.out", "w", stdout);
scanf("%ld %ld", &n, &m);
for (i = 1; i <= m; ++i) {
scanf("%ld %ld %ld", &a, &b, &c);
G[a[i]].push_back(b[i]);
C[a[i]].push_back(c[i]);
}
fill(d + 2, d + n + 1, INF);
Q[++Q[0]] = 1;
for (i = 1; i <= Q[0]; ++i)
aux = G[Q[i]].size();
for (j = 0; j < aux; ++j)
if (d[Q[i]] + C[Q[i]][j] < d[G[Q[i]][j]]) {
d[G[Q[i]][j]] = d[Q[i]] + C[Q[i]][j];
if (V[G[Q[i]][j]] < n) Q[++Q[0]] = G[Q[i]][j], ++V[G[Q[i]][j]];
else {printf("Ciclu negativ!"); return 0;}
}
for (i = 2; i <= n; ++i) printf("%ld ", d[i]);
return 0;
}