Pagini recente » Profil mishudiac | Cod sursa (job #3199585)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
const int NMAX = 50'000;
const int inf = 1e9;
int n, m;
int u, v, w;
vector<pair<int, int> > adj[NMAX + 1];
queue<int> q;
int d[NMAX + 1];
int cnt[NMAX + 1];
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++) {
fin >> u >> v >> w;
adj[u].push_back({v, w});
}
for (int i = 1; i <= n; i++)
d[i] = inf;
d[1] = 0;
q.push(1);
bool ciclu_negativ = 0;
while (!q.empty() && !ciclu_negativ) {
v = q.front();
q.pop();
for (auto edge: adj[v]) {
int to = edge.first;
int w = edge.second;
if (d[v] + w < d[to]) {
d[to] = d[v] + w;
q.push(to);
cnt[to]++;
if (cnt[to] > n) {
ciclu_negativ = 1;
}
}
}
}
if (ciclu_negativ) {
fout << "Ciclu negativ!";
}
else {
for (int i = 2; i <= n; i++) {
fout << d[i] << ' ';
}
}
return 0;
}