Pagini recente » Atasamentele paginii Clasament 7778 | Cod sursa (job #1990828)
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("dij.in");
ofstream out("dij.out");
const int N=50001;
const int INF= 1000001000;
int d[N],m,n,c,pred[N];
bool sel[N];
priority_queue<pair<int,int> >h;
vector <pair<int,int> > a[N];
void djk(int x0){
int x,y;
for(int i=1;i<=n;i++){
d[i]=INF;
}
d[x0]=0;
h.push(make_pair(0,x0));
while(!h.empty()){
while(!h.empty() && sel[h.top().second]){
h.pop();
}
if(h.empty())
return;
x=h.top().second;
sel[x]=true;
for(int i=0;i<a[x].size();i++){
y=a[x][i].first;
c=a[x][i].second;
if(d[x]+c<d[y]){
d[y]=d[x]+c;
pred[y]=x;
h.push(make_pair(-d[y],y));
}
}
}
}
int main()
{ int x,y;
in>>n>>m;
for(int i=0;i<m;i++){
in>>x>>y>>c;
a[x].push_back(make_pair(y,c));
}
djk(1);
for(int i=2;i<=n;i++){
out<<d[i]<<" ";
}
return 0;
}