Pagini recente » Borderou de evaluare (job #478005) | Cod sursa (job #1402813) | Cod sursa (job #935838) | Borderou de evaluare (job #16726) | Cod sursa (job #2976755)
#include <bits/stdc++.h>
using namespace std;
const int nmx = 5e4 + 3;
vector<array<int,2>> ad[nmx];
int64_t d[nmx],inq[nmx];
#if 1
#define cin fin
#define cout fout
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#endif
int main(){
int n,m;
cin >> n >> m;
while(m--){
int u,v,c;
cin >> u >> v >> c;
ad[u].push_back({v,c});
}
queue<int> q;
fill(d,d+nmx,INT_MAX);
d[1] = 0;
inq[1] = 1;
q.push(1);
for(int i=1;i<=n+1;i++){
if(q.empty())
break;
int nd = q.front();
inq[nd] = 0;
q.pop();
for(auto& ed : ad[nd]){
int64_t to = ed[0], w = ed[1];
if(d[to] > d[nd] + w){
d[to] = d[nd] + w;
if(inq[to]==0){
q.push(to);
inq[to] = 1;
}
}
}
}
if(q.size()){
cout << "Ciclu negativ!";
return 0;
}
for(int i=2;i<=n;i++){
cout << d[i] << " ";
}
}