dijkstra

ソースコード

 1#include <vector>
 2#include <queue>
 3using namespace std;
 4
 5// dijkstra
 6namespace titan23 {
 7    /**
 8     * @brief dijkstra
 9     * 
10     * @tparam T weight type
11     * @param G weighted graph
12     * @param start start
13     * @param INF inf
14     * @return vector<T> dist from start
15     */
16    template<typename T>
17    vector<T> dijkstra(
18            const vector<vector<pair<int, T>>> &G,
19            const int start,
20            const T INF) {
21        vector<T> dist(n, INF);
22        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> hq;
23        hq.emplace(0, start);
24        dist[start] = 0;
25        while (!hq.empty()) {
26            auto [d, v] = hq.top();
27            hq.pop();
28            if (dist[v] < d) continue;
29            for (const auto &[x, c] : G[v]) {
30                if (dist[x] > d + c) {
31                    dist[x] = d + c;
32                    hq.emplace(dist[x], x);
33                }
34            }
35        }
36        return dist;
37    }
38}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/dijkstra.cpp