最短路
Dijkstra Vec
cpp
template <class D>
using Edges = std::vector<std::vector<std::pair<int, D>>>;
template <class D>
auto dijkstra(const Edges<D> &E, int s) {
int n = E.size();
std::vector<D> dis(n, std::numeric_limits<D>::max() / 2);
std::vector<int> from(n, -1);
std::vector<bool> vis(n);
dis[s] = 0, from[s] = s;
using pdi = std::pair<D, int>;
std::priority_queue<pdi, std::vector<pdi>, std::greater<pdi>> pq;
pq.emplace(0, s);
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (vis[u])
continue;
vis[u] = true;
for (auto [v, wi] : E[u]) {
D d2 = w + wi;
if (dis[v] > d2)
dis[v] = d2, from[v] = u, pq.emplace(d2, v);
}
}
return std::pair(dis, from);
}
auto get_path(const std::vector<int> &from, int x, int y) {
std::vector<int> r;
for (; x != y; y = from[y])
r.push_back(y);
r.push_back(y);
std::reverse(r.begin(), r.end());
return r;
}Bellman-Ford Vec
cpp
template <class D>
using Edges = std::vector<std::vector<std::pair<int, D>>>;
template <class D>
auto bellman_ford(const Edges<D> &E, int s) {
int n = E.size();
std::vector<D> dis(n, std::numeric_limits<D>::max() / 2);
std::vector<int> from(n, -1);
dis[s] = 0, from[s] = s;
bool flag = true;
for (int k = 0; k < n && flag; k++) {
flag = false;
for (int u = 0; u < n; u++) {
for (auto [v, w] : E[u]) {
int d2 = dis[u] + w;
if (dis[v] > d2)
dis[v] = d2, from[v] = u, flag = true;
}
}
}
return std::pair(dis, from);
}Floyd Adj
cpp
template <class D>
using Edges = vec2d<int>;
template <class D>
auto floyd(const Edges<D> &E) {
int n = E.x;
auto f = E;
vec2d<int> pass(n, n, -1);
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
D d2 = f[i][k] + f[k][j];
if (f[i][j] > d2)
f[i][j] = d2, pass[i][j] = k;
}
}
}
return std::pair(f, pass);
}
auto get_path(const vec2d<int> &pass, int x, int y) {
std::vector<int> path = {x};
std::function<void(int, int)> dfs = [&](int a, int b) {
if (pass[a][b] != -1) {
int p = pass[a][b];
dfs(a, p), path.push_back(p), dfs(p, b);
}
};
if (x != y)
dfs(x, y), path.push_back(y);
return path;
}