typedef pair pii; // (距离, 目标节点)

vector> graph;

// 添加边

void addEdge(int u, int v, int weight) {

  graph[u].push_back({weight, v});

}

vector dist(n, INT_MAX);

priority_queue, greater> pq; // 小顶堆

dist[start] = 0;

pq.push({0, start});

while (!pq.empty()) {

  int u = pq.top().second;

  int d = pq.top().first;

  pq.pop();

  if (d > dist[u]) continue; // 已找到更短路径，跳过

  for (auto& edge : graph[u]) {

    int v = edge.second;

    int w = edge.first;

    if (dist[u] + w

      dist[v] = dist[u] + w;

      pq.push({dist[v], v});

    }

  }

}

#include

using namespace std;

void dijkstra(vector>& graph, int start, vector& dist) {

  int n = graph.size();

  dist.assign(n, INT_MAX);

  dist[start] = 0;

  priority_queue, greater> pq;

  pq.push({0, start});

  while (!pq.empty()) {

    int u = pq.top().second;

    int d = pq.top().first;

    pq.pop();

    if (d != dist[u]) continue;

    for (auto& edge : graph[u]) {

      int v = edge.second;

      int w = edge.first;

      if (dist[u] + w

        dist[v] = dist[u] + w;

        pq.push({dist[v], v});

      }

    }

  }

}