src/Dijkstra.hpp

View this file on GitHub
Last update: 2021-02-22 09:25:55+09:00
Include: #include "src/Dijkstra.hpp"

Depends on

Verified with

test/aoj/GRL_1_A.test.cpp

Code

#pragma once

#include <vector>
#include <algorithm>
#include <queue>

#include "chmin.hpp"
#include "Edge.hpp"

using namespace std;

template<class T>
vector<T> Dijkstra(const vector<vector<Edge<T>>> &edges, const int st) {

    const int V = (int)edges.size();
    const T inf = numeric_limits<T>::max() / 2;
    vector<T> cost(V, inf);
    cost[st] = 0;

    priority_queue <Edge<T>, vector<Edge<T>>, greater<>> pq;
    pq.emplace(st, cost[st]);

    while (!pq.empty()) {

        Edge<T> now(pq.top().to, pq.top().cost);
        pq.pop();

        if (cost[now.to] < now.cost) continue;
        for (const Edge<T> &e : edges[now.to]) {
            T tmp_cost = now.cost + e.cost;
            if (chmin(cost[e.to], tmp_cost)) {
                pq.emplace(e.to, cost[e.to]);
            }
        }
    }

    return cost; // min cost to vertex idx from st
}

#line 2 "src/Dijkstra.hpp"

#include <vector>
#include <algorithm>
#include <queue>

#line 2 "src/chmin.hpp"

template<class T>
inline bool chmin(T &a, const T b) { return a > b && (a = b, true); }
#line 2 "src/Edge.hpp"

template<class T>
struct Edge {
    int from{}, to{};
    T cost;
    Edge() = default;
    Edge(int to, T cost) : to(to), cost(move(cost)) {}
    Edge(int from, int to, T cost) : from(from), to(to), cost(move(cost)) {}
    bool operator>(const Edge &r) const { return this->cost > r.cost; }
};
#line 9 "src/Dijkstra.hpp"

using namespace std;

template<class T>
vector<T> Dijkstra(const vector<vector<Edge<T>>> &edges, const int st) {

    const int V = (int)edges.size();
    const T inf = numeric_limits<T>::max() / 2;
    vector<T> cost(V, inf);
    cost[st] = 0;

    priority_queue <Edge<T>, vector<Edge<T>>, greater<>> pq;
    pq.emplace(st, cost[st]);

    while (!pq.empty()) {

        Edge<T> now(pq.top().to, pq.top().cost);
        pq.pop();

        if (cost[now.to] < now.cost) continue;
        for (const Edge<T> &e : edges[now.to]) {
            T tmp_cost = now.cost + e.cost;
            if (chmin(cost[e.to], tmp_cost)) {
                pq.emplace(e.to, cost[e.to]);
            }
        }
    }

    return cost; // min cost to vertex idx from st
}