This documentation is automatically generated by competitive-verifier/competitive-verifier
View the Project on GitHub competitive-verifier/zzz_Nafmo2_library
#include "graph/dijkstra.hpp"
単一始点最短経路問題を解くことができるアルゴリズムです。
やきとりくんを参考にしました。ありがとうございます。
dijkstra(G, x)
: グラフ $G$ における $x$ を始点とするそれぞれの頂点への最短距離を求めます。shortest_path(G, s, t)
: グラフ $G$ における $s$ から $t$ への最短パスを求めます。頂点数を $V$、辺の数を $E$ とすると、
dijkstra(G, x)
: $O((E + V) \log V)$shortest_path(G, s, t)
: $O((E + V) \log V)$#pragma once
/**
* @brief Dijkstra's Algorithm (ダイクストラ法)
*
*/
template <typename T>
vector<long long> dijkstra(const vector<vector<array<long long, 2>>> &G, T x){
const long long INF = 9e18 / 2;
vector<long long> cost((int) G.size(), INF);
using P = pair<long long, long long>;
priority_queue<P, vector<P>, greater<>> q;
cost[x] = 0;
q.emplace(0, x);
while(q.size()){
auto [c, at] = q.top();
q.pop();
if(c > cost[at]) continue;
for(auto& [to, t] : G[at]){
if(cost[to] > c + t){
cost[to] = c + t;
q.emplace(cost[to], to);
}
}
}
return cost;
}
pair<long long, vector<pair<int, int>>> shortest_path(const vector<vector<array<long long, 2>>> &G, int s, int t){
const long long INF = 9e18 / 2;
vector<long long> cost((int) G.size(), INF);
vector<int> par((int) G.size(), -1);
using P = pair<long long, long long>;
priority_queue<P, vector<P>, greater<>> q;
cost[s] = 0;
par[s] = -1;
q.emplace(0, s);
while(q.size()){
auto [c, at] = q.top();
q.pop();
if(c > cost[at]) continue;
for(auto& [to, t] : G[at]){
if(cost[to] > c + t){
par[to] = at;
cost[to] = c + t;
q.emplace(cost[to], to);
}
}
}
if(cost[t] == INF){
return {-1, {}};
}
vector<pair<int, int>> path;
int now = t;
while(par[now] != -1){
path.emplace_back(par[now], now);
now = par[now];
}
reverse(path.begin(), path.end());
return {cost[t], path};
}
#line 2 "graph/dijkstra.hpp"
/**
* @brief Dijkstra's Algorithm (ダイクストラ法)
*
*/
template <typename T>
vector<long long> dijkstra(const vector<vector<array<long long, 2>>> &G, T x){
const long long INF = 9e18 / 2;
vector<long long> cost((int) G.size(), INF);
using P = pair<long long, long long>;
priority_queue<P, vector<P>, greater<>> q;
cost[x] = 0;
q.emplace(0, x);
while(q.size()){
auto [c, at] = q.top();
q.pop();
if(c > cost[at]) continue;
for(auto& [to, t] : G[at]){
if(cost[to] > c + t){
cost[to] = c + t;
q.emplace(cost[to], to);
}
}
}
return cost;
}
pair<long long, vector<pair<int, int>>> shortest_path(const vector<vector<array<long long, 2>>> &G, int s, int t){
const long long INF = 9e18 / 2;
vector<long long> cost((int) G.size(), INF);
vector<int> par((int) G.size(), -1);
using P = pair<long long, long long>;
priority_queue<P, vector<P>, greater<>> q;
cost[s] = 0;
par[s] = -1;
q.emplace(0, s);
while(q.size()){
auto [c, at] = q.top();
q.pop();
if(c > cost[at]) continue;
for(auto& [to, t] : G[at]){
if(cost[to] > c + t){
par[to] = at;
cost[to] = c + t;
q.emplace(cost[to], to);
}
}
}
if(cost[t] == INF){
return {-1, {}};
}
vector<pair<int, int>> path;
int now = t;
while(par[now] != -1){
path.emplace_back(par[now], now);
now = par[now];
}
reverse(path.begin(), path.end());
return {cost[t], path};
}