Pagini recente » Cod sursa (job #1682607) | Cod sursa (job #1494324) | Cod sursa (job #2418836) | Cod sursa (job #2267819) | Cod sursa (job #1488410)
#include <queue>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
vector<pair<int, int>> g[50001];
int d[50001];
int v[50001];
void dijk(){
int x;
d[1] = 0;
priority_queue<pair<int, int>> q;
q.push(pair<int, int>(0, 1));
while (!q.empty()){
x = q.top().second;
q.pop();
for (auto& i : g[x])
if (d[i.second]>d[x] + i.first){
d[i.second] = d[x] + i.first;
q.push(make_pair(d[i.second], i.second));
}
}
}
int main(){
ifstream f("dijkstra.in");
ofstream of("dijkstra.out");
int a, b, c, N, M;
f >> N >> M;
for (int i = 0; i < M; ++i){
f >> a >> b >> c;
g[a].push_back(pair<int, int>(c, b));
}
for (int i = 2; i <= N; ++i)d[i] = 200000000;
d[1] = 0;
dijk();
for (int i = 2; i <= N; ++i)
if (d[i] == 200000000)of << 0 << " ";
else
of << d[i] << " ";
}