Pagini recente » Borderou de evaluare (job #1241709) | Borderou de evaluare (job #1492642) | Cod sursa (job #862965)
Cod sursa(job #862965)
#include<fstream>
#include<vector>
#include<queue>
#define inf 100000000
#define dmax 250009
#define DMAX 50009
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, nr[dmax],cmin[DMAX];
queue<int> q;
struct nod_cost
{
int x,cost,ord;
};vector<nod_cost> vf[DMAX];
void citire();
void bellman_ford();
void afisare();
int main()
{
citire();
bellman_ford();
return 0;
}
void citire()
{
int x,y,c,i;
nod_cost s;
fin>>n>>m;
for(i=1; i<=m; i++)
{
fin>>x>>y>>c;
s.cost=c;
s.ord=i;
s.x=y;
vf[x].push_back(s);
}
for(i=1;i<=n;i++)
cmin[i]=inf;
}
void bellman_ford()
{
int i,op=0,nod;
nod_cost s;
q.push(1);
cmin[1]=0;
while(!op && !q.empty())
{
nod=q.front();
q.pop();
for(i=0;i<vf[nod].size();i++)
{
s=vf[nod][i];
if(cmin[nod]+s.cost<cmin[s.x])
{
cmin[s.x]=cmin[nod]+s.cost;
q.push(s.x);
nr[s.ord]++;
if (nr[s.ord]==n)
{
op=1;
break;
}
}
}
}
if(op)
fout<<"Ciclu negativ!";
else
afisare();
}
void afisare()
{
int i;
for(i=2;i<=n;i++)
fout<<cmin[i]<<' ';
}