ダイクストラ法(一つ前に通った頂点の情報付き)
(graph/dijkstra-with-walk.hpp)

• View this file on GitHub
• Last update: 2022-12-30 04:18:31+09:00
• Include: #include "graph/dijkstra-with-walk.hpp"
• Link: View error logs on GitHub Actions

Verified with

• verify/LC-ShortestPath.test.cpp

Code

pair<vector<ll>, vector<ll>> dijkstraWithWalk(CostGraph& g, int s){
  int n = g.size();
  vector<ll> dist(n, LLINF);
  vector<ll> walk(n);
  priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
  pq.emplace(0, s);
  while(!pq.empty()){
    auto [nowCost, now] = pq.top(); pq.pop();
    if(dist[now] < nowCost) continue;
    for(auto [to, cost]: g[now]) {
      if(chmin(dist[to], nowCost + cost)) {
        pq.emplace(nowCost + cost, to);
        walk[to] = now;
      }
    }
  }
  return {dist, walk};
}

#line 1 "graph/dijkstra-with-walk.hpp"
pair<vector<ll>, vector<ll>> dijkstraWithWalk(CostGraph& g, int s){
  int n = g.size();
  vector<ll> dist(n, LLINF);
  vector<ll> walk(n);
  priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
  pq.emplace(0, s);
  while(!pq.empty()){
    auto [nowCost, now] = pq.top(); pq.pop();
    if(dist[now] < nowCost) continue;
    for(auto [to, cost]: g[now]) {
      if(chmin(dist[to], nowCost + cost)) {
        pq.emplace(nowCost + cost, to);
        walk[to] = now;
      }
    }
  }
  return {dist, walk};
}

Back to top page