Cod sursa(job #1929639)

Utilizator Data 17 martie 2017 20:57:31 Algoritmul Bellman-Ford 100 cpp done Arhiva educationala 1.58 kb
``````#include <iostream>
#include <climits>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int NMax = 1e5 + 5;

int N,M;
int dist[NMax];

struct muchie {
int y,c;
muchie() {
muchie(1,0);
}
muchie(int a,int b) {
y = a;
c = b;
}
};
vector<muchie> v[NMax];

int main() {
in>>N>>M;
for (int i=1;i<=M;++i) {
int x,y,c;
in>>x>>y>>c;
muchie e(y,c);
v[x].push_back(e);
}

for (int i=2;i<=N;++i) {
dist[i] = 1e8;
}
dist[1] = 0;

bool cicluNegativ = false;
queue<int> Q;
Q.push(1);
while (Q.size()) {
int nod = Q.front();
Q.pop();
cicluNegativ = true;
break;
}
vector<muchie>::iterator it;
for (it = v[nod].begin();it < v[nod].end(); ++it) {
if (dist[it->y] > dist[nod] + (it->c)) {
dist[it->y] = dist[nod] + (it->c);
Q.push(it->y);
}
}
}
}

if (cicluNegativ) {
out<<"Ciclu negativ!";
}
else {
for (int i=2;i<=N;++i) {
out<<dist[i]<<' ';
}
return 0;
}

in.close();out.close();
return 0;
}
``````