Pagini recente » Borderou de evaluare (job #1782177) | Cod sursa (job #1802458)
#include <iostream>
#include <fstream>
#define inf 65536
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
int c[3000000],inc=1,sf=1,d[50001],viz[50001];//coada+distante(sol)+vizitat
struct nod{
int vecin;
int val;
struct nod *urm;
}*l[50001],*actual;
bool bellmanford(int k){
c[inc]=1;
for(int i=1;i<=n;++i)
d[i]=inf;
d[k]=0;
while(inc<=sf){
actual=l[c[inc]];
while(actual!=NULL){
if(actual->val+d[c[inc]]<d[actual->vecin] && d[c[inc]]!=inf && viz[actual->vecin]!=n-1){
d[actual->vecin]=actual->val+d[c[inc]];
++sf;
c[sf]=actual->vecin;
++viz[actual->vecin];
if(viz[actual->vecin]==n-1)
return false;
}
actual=actual->urm;
}
++inc;
}
return true;
}
int main()
{
in>>n>>m;
int x,y,valt;
for(int i=1;i<=m;++i){
in>>x>>y>>valt;
actual=new nod;
actual->vecin=y;
actual->urm=l[x];
actual->val=valt;
l[x]=actual;
}
bool ok=bellmanford(1);
if(ok==false)
out<<"Ciclu negativ!";
else
for(int i=2;i<=n;i++)
out<<d[i]<<" ";
return 0;
}