对于稀疏图时间复杂度更低的进阶版 Dijkstra Algorithm!

Time Complexity: $O(mlogm)$

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

using namespace std;
const int INF = 0x3f3f3f3f;

int n, m, u, v, w;

int dijkstra(vector<vector<pair<int, int>>>& g, int s) {

  vector<int> seen(n + 1);
  vector<int> dist(n + 1, INF);
  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()) {
    const auto [d, u] = pq.top(); pq.pop();
    if (seen[u]) continue;
    seen[u] = 1;

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

  return dist[n] == INF ? -1 : dist[n];
}

int main(void) {
  scanf("%d %d", &n, &m);
  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);
  }

  return printf("%d\n", dijkstra(g, 1)), 0;
}