图论
最短路
struct SPFA {
vector<i64> dis;
vector<bool> vis;
vector<int> from;
int n;
SPFA(vector<vector<pair<int, i64>>> &g, int s) : n(g.size()) {
dis.assign(n, INF), vis.assign(n, false), from.assign(n, -1);
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> q;
q.push({0, s}), dis[s] = 0;
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto &[v, w] : g[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
from[v] = u;
q.push({dis[v], v});
}
}
}
}
};