Cod sursa(job #894964)
#include<cstdio>
#define inf 210000000
using namespace std;
FILE *fin= fopen("bellman-ford.in", "r");
FILE *fout=fopen("bellman-ford.out","w");
struct nod
{
int nr,cost;
nod *next;
}*p,*l[100];
int i,j,n,m,c,d[100];
int minimize()
{
int ok=0;
for(int j=1;j<=n;++j)
while(l[j])
{
if(d[l[j]->nr]>d[j]+l[j]->cost)
{
ok=1;
d[l[j]->nr]=d[j]+l[j]->cost;
}
l[j]=l[j]->next;
}
return ok;
}
int main()
{
fscanf(fin,"%d%d",&n,&m);
for(int ii=1;ii<=n;++ii)
{
fscanf(fin,"%d%d%d",&i,&j,&c);
p=new nod;
p->next=l[i]; p->nr=j; p->cost=c; l[i]=p;
}
for(i=2;i<=n;++i)
d[i]=inf;
for(i=1;i<=n-1;++i)
minimize();
int ok=minimize();
if(ok)
fprintf(fout,"Ciclu negativ!");
else
for(i=2;i<=n;++i)
fprintf(fout,"%d ",d[i]);
return 0;
}