Cod sursa(job #2917988)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 9 august 2022 00:06:06
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <cstdio>
#include <queue>
#include <tuple>
#define INF 0x3f3f3f3f

std::vector<std::vector<std::pair<int,int>>> G; // G[i] -> (c, j) = (i -c-> j)
std::vector<int> DP;
std::priority_queue<std::pair<int, int>> PQ;
int N, M;

void dijkstra(int k)
{
  DP.resize(N);
  fill(DP.begin(), DP.end(), INF);
  DP[k] = 0;
  PQ.emplace(-0, k);

  int cost;
  while (!PQ.empty()) {
    std::tie(cost, k) = PQ.top();
    cost *= -1;
    PQ.pop();

    if (DP[k] != cost) continue;

    for (auto it: G[k])
      if (DP[it.second] > DP[k] + it.first) {
	DP[it.second] = DP[k] + it.first;
	PQ.emplace(-DP[it.second], it.second);
      }
  }

  for (int i = 1; i < N; ++i)
    if (DP[i] >= INF)
      printf("0 ");
    else
      printf("%d ", DP[i]);
}

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

  scanf("%d%d", &N, &M);
  G.resize(N);
  int a, b, c;
  for (int i = 0; i < M; ++i) {
    scanf("%d%d%d", &a, &b, &c);
    --a; --b;
    G[a].emplace_back(c, b);
  }

  dijkstra(0);
  
  return 0;
}