Cod sursa(job #1650010)

Utilizator Data 11 martie 2016 16:10:10 Algoritmul Bellman-Ford 100 cpp done Arhiva educationala 1.06 kb
``````#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define nmax 50009
#define INF 999999
using namespace std;
int n,m,sol[nmax],v[nmax],g=1;
queue<int> q;
vector<pair <int,int> >G[nmax];
inline void soll(){
int i,k;
for(i=1;i<=n;i++)
sol[i]=INF;
sol[1]=0;
q.push(1);
while(!q.empty()&&g){
k=q.front();
q.pop();
for(i=0;i<G[k].size();i++)
if((sol[G[k][i].first] > sol[k]+G[k][i].second)){
v[G[k][i].first]++;
if(v[G[k][i].first]>n) g=0;
q.push(G[k][i].first);
sol[G[k][i].first]= sol[k]+G[k][i].second;
}
}
}
inline void Afis(){
for(int i=1;i<=n;i++)
if(!g) {cout<<"Ciclu negativ!";return;}
for(int i = 2;i<=n;i++)
cout << sol[i]<<' ';
}
int main(){
int x,y,cost;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d%d",&x,&y,&cost);
G[x].push_back(make_pair(y,cost));
}
soll();
Afis();
return 0;
}
``````