Pagini recente » Cod sursa (job #3274131) | Cod sursa (job #704605) | Cod sursa (job #2128817) | Cod sursa (job #635471) | Cod sursa (job #2061988)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int maxn=(1<<30);
queue <int> q;
vector <int> v[50010],c[50010];
int sol[50010],trec[50010], i, n, m, ciclu,aux,next;
int main()
{
f>>n>>m;
for (i=1;i<=m;i++)
{
int x,y ,z;
f>>x>>y>>z;
v[x].push_back(y);
c[x].push_back(z);
}
for (i=2;i<=n;i++)
{
sol[i]=maxn;
}
q.push(1);
while (!q.empty())
{
aux=q.front();
q.pop();
trec[aux]++;
if (trec[aux]>n) {ciclu=1;break;}
for (i=0;i<v[aux].size();i++)
{
next=v[aux][i];
if (sol[next]>sol[aux]+c[aux][i]) {
sol[next]=sol[aux]+c[aux][i];
trec[next]++;
q.push(next);
}
// if (trec[next]>n) {ciclu=1;break;}
}
}
if (ciclu==1) g<<"Ciclu negativ!";
else for (i=2;i<=n;i++) g<<sol[i]<<" ";
return 0;
}