单源最短路径
Graph
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
const int n;
std::vector<edge> edges;
std::vector<std::vector<int>> g;
graph(int _n) : n(_n), g(_n) {}
virtual int add(int from, int to, T cost) = 0;
};
template <typename T>
class digraph : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
digraph(int _n) : graph<T>(_n) {}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
g[from].push_back(id);
edges.push_back({from, to, cost});
return id;
}
digraph<T> reverse() const {
digraph<T> rev(n);
for (auto &e : edges) {
rev.add(e.to, e.from, e.cost);
}
return rev;
}
};
template <typename T>
class undigraph : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
undigraph(int _n) : graph<T>(_n) {}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
g[from].push_back(id);
g[to].push_back(id);
edges.push_back({from, to, cost});
return id;
}
};
- dijkstra
template <typename T>
std::vector<T> dijkstra(const graph<T>& g, int st) {
assert(0 <= st && st < g.n);
std::vector<T> dist(g.n, std::numeric_limits<T>::max());
std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>> > q;
dist[st] = 0;
q.emplace(dist[st], st);
while (!q.empty()) {
T expected = q.top().first;
int u = q.top().second; q.pop();
if (dist[u] != expected) {
continue ;
}
for (int id : g.g[u]) {
auto& e = g.edges[id];
int to = e.from ^ e.to ^ u;
if (dist[to] > dist[u] + e.cost) {
dist[to] = dist[u] + e.cost;
q.emplace(dist[to], to);
}
}
}
return dist;
// returns numeric_limits<T>::max() if there's no path
}
最后更新:
2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42