Mai intai trebuie sa te autentifici.
Cod sursa(job #2302328)
Utilizator | Data | 14 decembrie 2018 10:40:24 | |
---|---|---|---|
Problema | Algoritmul Bellman-Ford | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.95 kb |
#include<cstdio>
const int N=50001;
int m,n,i,k,l,r,d[N],e[7*N],v[N],u[N],*g[N],*h[N],w[N],j;
int main()
{
freopen("bellmanford.in","r",stdin),freopen("bellmanford.out","w",stdout),scanf("%d%d",&n,&m);
while(m--)
scanf("%d%d%d",&k,&l,&r),w[k]++;
for(i=1;i<=n;w[i++]=0)
d[i]=N,g[i]=h[i]=new int[w[i]];
fseek(stdin,0,SEEK_SET),scanf("%d%d",&n,&m);
while(m--)
scanf("%d%d%d",&k,&l,&r),g[k][w[k]]=l,h[k][w[k]++]=r;
for(k=l=r=d[1]=0,e[r++]=v[1]=1;l<r&&!k;)
for(i=e[l++],v[i]=j=0;j<w[i]&&!k;j++)
if(d[g[i][j]]>d[i]+h[i][j])
{
d[g[i][j]]=d[i]+h[i][j];
if(!v[g[i][j]])
if(u[g[i][j]]>n)
k=1;
else
e[r++]=g[i][j],v[g[i][j]]=1,u[g[i][j]]++;
}
if(k)
printf("Ciclu negativ!");
else
for(i=2;i<=n;i++)
printf("%d ",d[i]);
}