Cod sursa(job #895460)
#include<cstdio>
#include<cstdlib>
#include<list>
#include<vector>
#include<queue>
#define inf 21000000
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,c,n,m,viz[50002],app[50002],k;
list<nod> lista;
list<nod>::iterator it;
vector< list<nod> > l(50002,lista);
vector<int> d(50002,inf);
vector<nod> heap(50002);
int bellmanford()
{
int i,j,c;
d[1]=0;
q.nr=1; q.cost=d[1];
viz[1]=1; app[1]=1;
heap.push_back(q);
while(k<heap.end()-heap.begin())
{
i=heap[k].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];
heap.push_back(q);
}
}
}
++k;
}
return 0;
}
int main()
{
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;++i)
{
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;
}