【模板】堆优化Dijkstra

Dij的核心思想：全局最小值不会被其他节点更新，因此得到最小值后只需要扩展一次即可。
概念：扩展、出队
注意：vis[ ]数组表示的是每个节点是否扩展过，因此开始时vis[st]不置1。
时间复杂度(O(m*log(n)))

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;

int n, m, s, d[N];
bool vis[N];
priority_queue<pair<int, int>> q;

struct edge {
  int next, to, w;
} e[M << 1];
int tot = 1, head[N];
void add_edge(int x, int y, int w) {
  e[++tot] = edge{head[x], y, w}, head[x] = tot;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  cin >> n >> m >> s;
  
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    add_edge(x, y, z);
  }
  
  fill(d + 1, d + n + 1, 0x3f3f3f3f);
  
  d[s] = 0;
  q.push({0, s});
  
  while (q.size()) {
    int x = q.top().second;
    q.pop();
    if (vis[x] == true) continue;
    vis[x] = true;
    for (int i = head[x]; i; i = e[i].next) {
      int y = e[i].to, w = e[i].w;
      if (d[y] > d[x] + w) {
        d[y] = d[x] + w;
        q.push({-d[y], y});
      }
    }
  }
  
  for (int i = 1; i <= n; i++) {
    cout << d[i] << " ";
  }
  
  return 0;
}