Pagini recente » Monitorul de evaluare | Cod sursa (job #67771) | Borderou de evaluare (job #2395632) | Cod sursa (job #2311431)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define NMax 50010
#define inf (1 << 30) - 1
int n, m;
vector< pair<int, int> > G[NMax];
int d[NMax];
struct Cmp{
bool operator()(int a, int b){
return d[a] > d[b];
}
};
priority_queue<int, vector<int>, Cmp> q;
void init();
void dijkstra();
void afisare();
int main(){
init();
dijkstra();
afisare();
}
void init(){
int i, x, y, c;
fin >> n >> m;
for(i = 1; i <= m; i++){
fin >> x >> y >> c;
G[x].push_back(make_pair(y, c));
}
for(i = 2; i <= n; i++)
d[i] = inf;
}
void dijkstra(){
int i, j, x;
q.push(1);
while(!q.empty()){
x = q.top(); q.pop();
for(j = 0; j < G[x].size(); j++)
if(d[G[x][j].first] > d[x] + G[x][j].second){
d[G[x][j].first] = d[x] + G[x][j].second;
q.push(G[x][j].first);
}
}
}
void afisare(){
for(int i = 2; i <= n; i++)
fout << (d[i] == inf ? 0 : d[i]) << ' ';
}