単一始点最短経路(ダイクストラ法)
(graph/dijkstra-with-cost.hpp)

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

Verified with

• verify/AOJ-GRL_1_A.test.cpp

Code

vector<ll> dijkstraWithCost(CostGraph& G, int s){
  int n = G.size();
  vector<ll> dist(n, LLINF);
  dist[s] = 0;
  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);
    }
  }
  return dist;
}

#line 1 "graph/dijkstra-with-cost.hpp"
vector<ll> dijkstraWithCost(CostGraph& G, int s){
  int n = G.size();
  vector<ll> dist(n, LLINF);
  dist[s] = 0;
  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);
    }
  }
  return dist;
}

Back to top page