Cod sursa(job #2409654)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 19 aprilie 2019 12:32:36
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
using namespace std;

const int DIM = 50005;
const int INF = 2000000005;

int dp[DIM];

vector<pair<int, int> > edg[DIM];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > prq;

int main(void)
{
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  int n, m; cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x, y, c; cin >> x >> y >> c;
    edg[x].push_back(make_pair(y, c)); }
  for (int i = 2; i <= n; ++i) {
    dp[i] = INF; }
  prq.push(make_pair(0, 1));
  while (prq.size()) {
    int d = prq.top().first,
        x = prq.top().second;
    prq.pop();
    if (d > dp[x]) {
      continue; }
    for (pair<int, int> it : edg[x]) {
      int y = it.first, c = it.second;
      if (dp[y] > dp[x] + c) {
        dp[y] = dp[x] + c;
        prq.push(make_pair(dp[y], y)); } } }
  for (int i = 2; i <= n; ++i) {
    if (dp[i] == INF) {
      dp[i] = 0; }
    cout << dp[i] << " "; }
  return 0;
}