dijkstra

发表于 分类于 ， 阅读次数： 本文字数： 399 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
auto dijkstra = [&](int s) {
  vector<i64> dis(n, 1e18);
  dis[s] = 0;
  priority_queue<pll, vector<pll>, greater<pll>> q;
  q.push({0, s});

  while (!q.empty()) {
    auto [d, u] = q.top();
    q.pop();

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

    for (auto [v, w] : v[u]) {
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
  return dis;
};