/
dijkstra.hpp
84 lines (75 loc) · 1.84 KB
/
dijkstra.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#pragma once
#include "graph/base.hpp"
template <typename T, typename GT>
pair<vc<T>, vc<int>> dijkstra_dense(GT& G, int s) {
const int N = G.N;
vc<T> dist(N, infty<T>);
vc<int> par(N, -1);
vc<bool> done(N);
dist[s] = 0;
while (1) {
int v = -1;
T mi = infty<T>;
FOR(i, N) {
if (!done[i] && chmin(mi, dist[i])) v = i;
}
if (v == -1) break;
done[v] = 1;
for (auto&& e: G[v]) {
if (chmin(dist[e.to], dist[v] + e.cost)) par[e.to] = v;
}
}
return {dist, par};
}
template <typename T, typename GT, bool DENSE = false>
pair<vc<T>, vc<int>> dijkstra(GT& G, int v) {
if (DENSE) return dijkstra_dense<T>(G, v);
auto N = G.N;
vector<T> dist(N, infty<T>);
vector<int> par(N, -1);
using P = pair<T, int>;
priority_queue<P, vector<P>, greater<P>> que;
dist[v] = 0;
que.emplace(0, v);
while (!que.empty()) {
auto [dv, v] = que.top();
que.pop();
if (dv > dist[v]) continue;
for (auto&& e: G[v]) {
if (chmin(dist[e.to], dist[e.frm] + e.cost)) {
par[e.to] = e.frm;
que.emplace(dist[e.to], e.to);
}
}
}
return {dist, par};
}
// 多点スタート。[dist, par, root]
template <typename T, typename GT>
tuple<vc<T>, vc<int>, vc<int>> dijkstra(GT& G, vc<int> vs) {
assert(G.is_prepared());
int N = G.N;
vc<T> dist(N, infty<T>);
vc<int> par(N, -1);
vc<int> root(N, -1);
using P = pair<T, int>;
priority_queue<P, vector<P>, greater<P>> que;
for (auto&& v: vs) {
dist[v] = 0;
root[v] = v;
que.emplace(T(0), v);
}
while (!que.empty()) {
auto [dv, v] = que.top();
que.pop();
if (dv > dist[v]) continue;
for (auto&& e: G[v]) {
if (chmin(dist[e.to], dist[e.frm] + e.cost)) {
root[e.to] = root[e.frm];
par[e.to] = e.frm;
que.push(mp(dist[e.to], e.to));
}
}
}
return {dist, par, root};
}