Pagini recente » Cod sursa (job #9144) | Borderou de evaluare (job #103428) | Cod sursa (job #2976760)
#include <bits/stdc++.h>
using namespace std;
const int nmx = 5e4 + 3;
vector<array<int,2>> ad[nmx];
#if 1
#define cin fin
#define cout fout
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#endif
const int64_t INF = 1e17;
int n,m;
bool spfa(vector<int64_t>& d) {
d.assign(n, INF);
vector<int> cnt(n, 0);
vector<bool> inqueue(n, false);
queue<int> q;
d[1] = 0;
q.push(1);
inqueue[1] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
inqueue[v] = false;
for (auto edge : ad[v]) {
int to = edge[0];
int64_t len = edge[1];
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
if (!inqueue[to]) {
q.push(to);
inqueue[to] = true;
cnt[to]++;
if (cnt[to] > n)
return false; // negative cycle
}
}
}
}
return true;
}
int main(){
cin >> n >> m;
while(m--){
int u,v,c;
cin >> u >> v >> c;
ad[u].push_back({v,c});
}
vector<int64_t> d(nmx,INF);
if(spfa(d)){
for(int i=2;i<=n;i++)
cout << d[i] << " ";
}else{
cout << "Ciclu negativ!";
}
}