This documentation is automatically generated by online-judge-tools/verification-helper
#include "ugilib/graph/dijkstra.hpp"
#pragma once
#include <bits/stdc++.h>
#include "ugilib/base/constants.hpp"
using namespace std;
namespace ugilib {
/**
* @brief ダイクストラ法
* @param n グラフの頂点数
* @param start 始点
* @param graph グラフ. vector<pair<int, weight_t>> で隣接頂点とコストを表す
* @param weight_inf 無限大の値. パスが存在しない場合のコスト
* @return 始点から各頂点までの最短距離
* @note O((E+V)logV)
*/
template<typename weight_t>
vector<weight_t> dijkstra(int n, int start, const vector<vector<pair<int, weight_t>>>& graph, const weight_t weight_inf = ugilib::constants::INF<weight_t>) {
vector<weight_t> costs(n, weight_inf);
costs[start] = 0;
priority_queue<pair<weight_t, int>, vector<pair<weight_t, int>>, greater<>> next_nodes;
next_nodes.push({0, start});
while (!next_nodes.empty()) {
auto [cost, node] = next_nodes.top(); next_nodes.pop();
if (cost > costs[node]) continue;
for (const auto [next_node, next_cost] : graph[node]) {
auto new_cost = cost + next_cost;
if (new_cost < costs[next_node]) {
costs[next_node] = new_cost;
next_nodes.push({costs[next_node], next_node});
}
}
}
return costs;
}
} // namespace ugilib
#line 2 "ugilib/graph/dijkstra.hpp"
#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++) // rep macro
#define all(v) begin(v), end(v) // all iterator
#line 3 "ugilib/base/constants.hpp"
namespace ugilib::constants {
template<typename T>
inline constexpr T INF = std::numeric_limits<T>::max() / 2;
} // namespace ugilib::constants
const ll INF = ugilib::constants::INF<ll>;
#line 4 "ugilib/graph/dijkstra.hpp"
using namespace std;
namespace ugilib {
/**
* @brief ダイクストラ法
* @param n グラフの頂点数
* @param start 始点
* @param graph グラフ. vector<pair<int, weight_t>> で隣接頂点とコストを表す
* @param weight_inf 無限大の値. パスが存在しない場合のコスト
* @return 始点から各頂点までの最短距離
* @note O((E+V)logV)
*/
template<typename weight_t>
vector<weight_t> dijkstra(int n, int start, const vector<vector<pair<int, weight_t>>>& graph, const weight_t weight_inf = ugilib::constants::INF<weight_t>) {
vector<weight_t> costs(n, weight_inf);
costs[start] = 0;
priority_queue<pair<weight_t, int>, vector<pair<weight_t, int>>, greater<>> next_nodes;
next_nodes.push({0, start});
while (!next_nodes.empty()) {
auto [cost, node] = next_nodes.top(); next_nodes.pop();
if (cost > costs[node]) continue;
for (const auto [next_node, next_cost] : graph[node]) {
auto new_cost = cost + next_cost;
if (new_cost < costs[next_node]) {
costs[next_node] = new_cost;
next_nodes.push({costs[next_node], next_node});
}
}
}
return costs;
}
} // namespace ugilib