单源最短路径

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