Dijkstra 7695da1b

Dijkstra's algorithm on a non-negative-weight directed graph given as an adjacency list. W needs operator+ and operator<.

Time: O((V + E) \log V). tested

content/graphs/dijkstra.h

template <typename W>
vector<W> dijkstra(int n, vector<vector<pair<int, W>>> &adj, int src, W INF) {
    vector<W> dist(n, INF);
    priority_queue<pair<W, int>, vector<pair<W, int>>, greater<>> pq;
    dist[src] = W();
    pq.push({dist[src], src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto &[v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}