This documentation is automatically generated by competitive-verifier/competitive-verifier
始点 $s$ から各頂点までの最短距離および最短経路を求める.
dijkstra(path, cost, s)
:隣接リスト path
,各辺の重み cost
,始点 s
の無向グラフに対しダイクストラ法を適用する.operator[](idx)
:始点 $s$ から頂点 $\mathrm{idx}$ までの最短距離を返す.get_path(t)
:始点 $s$ から頂点 $t$ までの最短経路を返す.頂点数を $n$,辺数を $m$ とする.
operator[](idx)
:$O(1)$get_path(t)
:$O(n)$#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#include "../structure/2d_array.cpp"
template<typename T> struct dijkstra {
using P = pair<long long, int>;
const long long inf = (1LL << 62) - 1;
private:
int n;
vector<long long> dist;
vector<int> prev;
public:
dijkstra(v2d<int> &path, v2d<T> &cost, int s) : n(path.size()), dist(n, inf), prev(n, -1) {
dist[s] = 0;
priority_queue<P, vector<P>, greater<P>> q;
q.emplace(0, s);
while(not q.empty()) {
auto [d, x] = q.top();
q.pop();
if(d > dist[x]) continue;
for(int i = 0; i < path[x].size(); i++) {
int nx = path[x][i];
long long nd = d + cost[x][i];
if(nd >= dist[nx]) continue;
dist[nx] = nd;
prev[nx] = x;
q.emplace(nd, nx);
}
}
}
inline long long operator[](int idx) {
return dist[idx];
}
vector<int> get_path(int t) {
vector<int> ans;
for(int x = t; x >= 0; x = prev[x]) ans.emplace_back(x);
return vector<int>(ans.rbegin(), ans.rend());
}
};
#line 2 "graph/dijkstra.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#line 2 "structure/2d_array.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct v2d {
private:
vector<vector<T>> m;
public:
v2d() {}
v2d(int h, int w) : m(h, vector<T>(w)) {}
v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}
void assign(int h, int w) {
m.assign(h, vector<T>(w));
}
void assign(int h, int w, const T init) {
m.assign(h, vector<T>(w, init));
}
inline int size() const {
return m.size();
}
void in() {
for(vector<T> &v : m)
for(T &val : v) cin >> val;
}
void in(int h, int w) {
m.resize(h, vector<T>(w));
in();
}
void out() {
int h = m.size();
for(vector<T> &v : m) {
int sz = v.size();
for(int j = 0; j < sz; j++) {
cout << v[j] << (j == sz - 1 ? '\n' : ' ');
}
}
cout << flush;
}
inline vector<T> &operator[](int idx) {
assert(0 <= idx && idx < m.size());
return m[idx];
}
bool rangeout(int x, int y) {
if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
return false;
}
};
#line 10 "graph/dijkstra.cpp"
template<typename T> struct dijkstra {
using P = pair<long long, int>;
const long long inf = (1LL << 62) - 1;
private:
int n;
vector<long long> dist;
vector<int> prev;
public:
dijkstra(v2d<int> &path, v2d<T> &cost, int s) : n(path.size()), dist(n, inf), prev(n, -1) {
dist[s] = 0;
priority_queue<P, vector<P>, greater<P>> q;
q.emplace(0, s);
while(not q.empty()) {
auto [d, x] = q.top();
q.pop();
if(d > dist[x]) continue;
for(int i = 0; i < path[x].size(); i++) {
int nx = path[x][i];
long long nd = d + cost[x][i];
if(nd >= dist[nx]) continue;
dist[nx] = nd;
prev[nx] = x;
q.emplace(nd, nx);
}
}
}
inline long long operator[](int idx) {
return dist[idx];
}
vector<int> get_path(int t) {
vector<int> ans;
for(int x = t; x >= 0; x = prev[x]) ans.emplace_back(x);
return vector<int>(ans.rbegin(), ans.rend());
}
};