Pagini recente » Cod sursa (job #1605724) | Cod sursa (job #3281) | Cod sursa (job #2287928) | Cod sursa (job #25157) | Cod sursa (job #2629157)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct elem
{
int destinatie,cost;
};
int n,m,dist[50005],viz[50005],ans[50005];
queue<int>q;
vector<elem>v[50005];
void bellmanford(int val)
{
int i;
q.push(val);
viz[val]=1;
while(!q.empty())
{
int nod=q.front();
viz[nod]=0;
q.pop();
for(i=0;i<v[nod].size();i++)
{
ans[nod]++;
if(ans[nod]>n)
{
fout<<"Ciclu negativ";
return;
}
int dest=v[nod][i].destinatie;
if(dist[dest]>v[nod][i].cost+dist[nod])
{
dist[dest]=v[nod][i].cost+dist[nod];
if(viz[dest]==0)
{
viz[dest]=1;
q.push(dest);
}
}
}
}
for(i=2;i<=n;i++)
fout<<dist[i]<<" ";
}
int main()
{
int i,x,y,z;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y>>z;
v[x].push_back({y,z});
}
for(i=2;i<=n;i++)
dist[i]=INT_MAX;
bellmanford(1);
return 0;
}