Cod sursa(job #901965)
#include<cstdio>
#include<cstdlib>
#include<list>
#include<vector>
#include<queue>
#define DMAX 1000
#define INF 210000
using namespace std;
FILE *fin= fopen("bellmanford.in", "r");
FILE *fout=fopen("bellmanford.out","w");
struct nod
{
int nr,cost;
}q;
class maimic
{
public:
bool operator()(nod a,nod b)
{
return a.cost<b.cost;
}
};
int i,j,n,m,ii,c,viz[DMAX],app[DMAX],k;
list<nod> lista;
vector< list<nod> > l(DMAX,lista);
vector<int> d(DMAX,INF);
vector<nod> v;
list<nod>::iterator it;
int bellmanford()
{
int i,j,c;
d[1]=0;
q.nr=1; q.cost=0; v.push_back(q);
viz[1]=1; ++app[1];
while(!v.empty())
{
i=v.begin()->nr;
viz[i]=0;
for(it=l[i].begin();it!=l[i].end();++it)
{
j=it->nr;
c=it->cost;
if(d[j]>d[i]+c)
{
d[j]=d[i]+c;
if(!viz[j])
{
if(app[j]>n)
return 1;
++app[j];
viz[j]=1;
q.nr=j;
q.cost=d[j];
v.push_back(q);
}
}
}
v.erase(v.begin());
}
return 0;
}
int main()
{
fscanf(fin,"%d%d",&n,&m);
for(ii=1;ii<=m;++ii)
{
fscanf(fin,"%d%d%d",&i,&j,&c);
q.nr=j; q.cost=c;
l[i].push_back(q);
}
if(bellmanford())
fprintf(fout,"Ciclu negativ!");
else
for(i=2;i<=n;++i)
fprintf(fout,"%d ",d[i]);
return 0;
}