# Cod sursa(job #1789203)

Utilizator Data 26 octombrie 2016 19:31:01 Algoritmul lui Dijkstra 100 cpp done Arhiva educationala 1.07 kb
``````#include <stdio.h>
#include <vector>
#include <set>
#include <queue>

#define maxdim 50005

using namespace std;

int n, m;
int dist[maxdim];
vector<pair<int, int>> G[maxdim];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> S;

int main() {
freopen("dijkstra.in", "r", stdin);
freopen("dijkstra.out", "w", stdout);

scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y, c; scanf("%d %d %d", &x, &y, &c);
G[x].push_back(make_pair(y, c));
}

for (int i = 2; i <= n; ++i) {
dist[i] = 1 << 30;
}
S.push(make_pair(dist[1], 1));
while (!S.empty()) {
auto p = S.top();
int nod = p.second, cost = p.first;
S.pop();
if (cost != dist[nod]) {
continue;
}

for (auto &v : G[nod]) {
if (dist[v.first] > dist[nod] + v.second) {
dist[v.first] = dist[nod] + v.second;
S.push(make_pair(dist[v.first], v.first));
}
}
}

for (int i = 2; i <= n; ++i) {
if (dist[i] == (1 << 30)) {
dist[i] = 0;
}
printf("%d ", dist[i]);
}
printf("\n");

return 0;
}

``````