个人算法模板——Dijkstra最短路
作者:
Andrew1729
,
2022-03-04 17:42:37
,
所有人可见
,
阅读 207
Dijkstra
使用例
template<class T = int>
struct Dijkstra {
int n;
const T INF;
typedef std::pair<int, T> pit;
typedef std::vector<std::vector<pit>> G;
G g;
Dijkstra(int n, const T& INF): n(n), g(n), INF(INF){}
Dijkstra(const G &g, const T& INF): g(g), INF(INF){}
void add(int a, int b, T c) {
g[a].emplace_back(b, c);
}
T run(int s, int t) {
std::vector<T> d(n, INF);
typedef std::pair<T, int> pti;
std::priority_queue<pti, std::vector<pti>, std::greater<pti>> q;
d[s] = 0;
q.emplace(d[s], s);
while (q.size()) {
auto [dist, u] = q.top(); q.pop();
if (dist != d[u]) continue;
for (auto &[v, w]: g[u]) {
int fina = d[u] + w;
if (d[v] > fina) {
d[v] = fina;
q.emplace(d[v], v);
}
}
}
return d[t] == INF ? -1 : d[t];
}
};