Pagini recente » Cod sursa (job #256815) | Diferente pentru utilizator/roarkaq30 intre reviziile 1 si 2 | Borderou de evaluare (job #2398497) | Cod sursa (job #2312106)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define NMax 50003
#define inf (1 << 30) - 1
#define pii pair<int, int>
int n, m;
vector< pii > G[NMax];
int d[NMax];
bitset<NMax> viz;
class Cmp{
public:
bool operator()(pii & a, pii & b){
return a.second > b.second;
}
};
priority_queue<pii, vector< pii >, Cmp> q;
int main(){
int i, j, 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;
q.push(make_pair(1, 0));
while(!q.empty()){
x = q.top().first; q.pop();
if(!viz[x]){
viz[x] = true;
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(make_pair(G[x][j].first, d[G[x][j].first]));
}
}
}
for(int i = 2; i <= n; i++)
fout << (d[i] == inf ? 0 : d[i]) << ' ';
}