Pagini recente » Cod sursa (job #1291201) | Cod sursa (job #301966) | Cod sursa (job #2605220) | Cod sursa (job #735751) | Cod sursa (job #1778885)
#define _USE_MATH_DEFINES
#include <fstream>
#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#define nmax 250005
using namespace std;
vector < pair <int,int> > v[nmax];
queue <int> q;
bool in_q[nmax];
int n,m;
int d[nmax],cnt_q[nmax];
int Push();
void Bellman_Ford();
int main(){
int x,y,cost;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y>>cost;
v[x].push_back(make_pair(y,cost));
}
Bellman_Ford();
for(int i=2;i<=n;i++)
cout<<(d[i]==INT_MAX?0:d[i])<<' ';
return 0;
}
inline void Push(int x){
cnt_q[x]++;
if(!in_q[x]&&cnt_q[x]<n){
q.push(x);
in_q[x]=1;
}
}
void Bellman_Ford(){
int now;
for(int i=0;i<=n;i++)
d[i]=INT_MAX;
Push(1);
d[1]=0;
while(!q.empty()){
now=q.front();
q.pop();
in_q[now]=0;
for(int i=0;i<v[now].size();i++){
int next=v[now][i].first;
int cost=v[now][i].second;
if(d[now]+cost<d[next]){
d[next]=d[now]+cost;
Push(next);
}
}
}
}