Cod sursa(job #2122010)

Utilizator tudormaximTudor Maxim tudormaxim Data 4 februarie 2018 15:33:53
Problema Algoritmul Bellman-Ford Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int maxn = 5e4 + 5;
const int oo = 1 << 30;
vector < pair <int, int> > G[maxn];
int Dist[maxn], Cnt[maxn];

bool Bellman(int start, int n) {
	vector < pair <int, int> > ::iterator it;
	bitset <maxn> Vis = 0;
	queue <int> Q;
	int node, i;
	for (i = 1; i <= n; i++) {
		Dist[i] = oo;
	}
	Dist[start] = 0;
	Q.push(start);
	while (!Q.empty()) {
		node = Q.front();
		Vis[node] = false;
		Q.pop();
		for (it = G[node].begin(); it != G[node].end(); it++) {
			if (Dist[it->first] > Dist[node] + it->second) {
				Dist[it->first] = Dist[node] + it->second;
				if (Vis[it->first] == false) {
					Vis[it->first] = true;
					Cnt[it->first]++;
					Q.push(it->first);
					if (Cnt[it->first] >= n) return 1;
				}
			}
		}
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	int n, m, x, y, c, i;
	fin >> n >> m;
	for (i = 1; i <= m; i++) {
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
	if (Bellman(1, n)) {
		fout << "Ciclu negativ!\n";
	}
	else {
		for (i = 2; i <= n; i++) {
			fout << Dist[i] << " ";
		}
	}
	fin.close();
	fout.close();
	return 0;
}