Cod sursa(job #901850)
#include<cstdio>
#include<cstdlib>
#include<list>
#include<vector>
#include<queue>
#define DMAX 50000
#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);
priority_queue< nod,vector<nod>,maimic> heap;
list<nod>::iterator it;
int bellmanford()
{
int i,j,c;
d[1]=0;
q.nr=1; q.cost=0; heap.push(q);
viz[1]=1; app[1]=1;
while(k<heap.size())
{
i=heap.top().nr;
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])
{
++app[j];
if(app[j]>n)
return 1;
viz[j]=1;
q.nr=j;
q.cost=d[j];
heap.push(q);
}
}
}
heap.pop();
}
return 0;
}
int main()
{
fscanf(fin,"%d%d",&n,&m);
for(ii=1;ii<=n;++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;
}