Dijkstra Algorithm

#include <iostream>
#include <vector>
#include <queue>

#define INF 0x3f3f3f3f

using namespace std;

int n, m, u, v, w, k, q, x;

// 应该用PriorityQueue版本的Dijkstra Algorithm
void dijkstra(vector<vector<pair<int, int>>>& g, vector<int>& dist, int s) {

  vector<int> visited(n + 1, 0); // 访问标记数组 
  dist[s] = 0;

  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  pq.emplace(0, s);

  while (not pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (visited[u]) continue;
    visited[u] = 1;

    for (const auto& [v, w] : g[u]) {
      if (visited[v]) continue;
      if (d + w < dist[v]) {
        dist[v] = d + w;
        pq.emplace(d + w, v);
      }
    }
  }
}

int main(void) {
  scanf("%d %d", &n, &m);

  // dijkstra's algorithm (三件套)
  vector<vector<pair<int, int>>> g(n + 1); // adjacency list

  while (m--) {
    scanf("%d %d %d", &u, &v, &w);
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }

  vector<int> dist(n + 1, INF); // 从源点出发到每个顶点的距离

  scanf("%d", &k);
  for (int i = 0; i < k; ++i) {
    scanf("%d", &x);
    g[0].emplace_back(x, 0);
  };

  dijkstra(g, dist, 0);
  scanf("%d", &q);
  while (q--) {
    scanf("%d", &x);
    printf("%d\n", dist[x]);
  }
  return 0;
}