Cod sursa(job #862047)
#include <fstream>
#define INF 1000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, start;
int cmin[5010], c[5010][5010];
int tata[5010];
int main()
{
int i, m, x, y, cost, j;
fin>>n>>m; start=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
c[i][j]=INF;
for(i=1;i<=m;i++)
{
fin>>x>>y>>cost;
c[x][y]=cost;
}
int schimb;
for(i=1;i<=n;i++)
cmin[i]=INF;
cmin[start]=0;
for(i=0;i<n;i++)
{
schimb=0;
for(j=1;j<=n;j++)
for(x=1;x<=n;x++)
if (cmin[j]!=INF&&c[j][x]!=INF)
if(cmin[x]>cmin[j]+c[j][x])
{
cmin[x]=cmin[j]+c[j][x];
tata[x]=j; schimb=1;
}
}
if(schimb)
fout<<"Ciclu negativ!"<<'\n';
else
for(i=2;i<=n;i++)
fout<<cmin[i]<<' ';
return 0;
}