Dijkstra - 多次元ダイクストラ
(lib/40-graph/Dijkstra.cpp)

• View this file on GitHub
• Last update: 2023-05-30 04:49:31+09:00

Verified with

• test/graph/Dijkstra-restore.test.cpp
• test/graph/Dijkstra.test.cpp

Code

/*
 * @title Dijkstra - 多次元ダイクストラ
 * @docs md/graph/Dijkstra.md
 */
template<class T> class Dijkstra {
    vector<long long> num_list;
    vector<long long> sum;
    int N;
    T inf;
    vector<vector<pair<T,int>>> edge;
    vector<T> cost;
    vector<int> dp;
    void resize(const int N) {
        edge.resize(N);
        cost.resize(N);
        dp.resize(N);
    }
public:
    Dijkstra(int N,T inf):inf(inf),num_list(1,N),sum(1,1),N(N){
        resize(N);
    }
    Dijkstra(initializer_list<long long> size_list,T inf):num_list(size_list),inf(inf),N(1){
        for(long long& e:num_list) N *= e;
        sum.resize(num_list.size(),1);
        for(int i = 0; i < num_list.size(); ++i) {
            for(int j = i + 1; j < num_list.size(); ++j) {
                sum[i] *= num_list[j];
            }
        }
        resize(N);
    }
    void make_edge(int from, int to, T w) {
        if(from < 0 || N <= from || to < 0 || N <= to) return;
        edge[from].push_back({ w,to });
    }
    void make_edge(initializer_list<long long> from_list, initializer_list<long long> to_list, T w) {
        int from = 0, to = 0;
        auto from_itr = from_list.begin(),to_itr = to_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            if(*from_itr < 0 || num_list[i] <= *from_itr || *to_itr < 0 || num_list[i] <= *to_itr) return;
            from += (*from_itr)*sum[i];
            to   += (*to_itr)*sum[i];
            from_itr++;
            to_itr++;
        }
        edge[from].push_back({ w,to });
    }
    void solve(initializer_list<long long> start_list) {
        int start = 0;
        auto start_itr = start_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            start += (*start_itr)*sum[i];
            start_itr++;
        }
        solve(start);
    }
    void solve(int start) {
        for(int i = 0; i < N; ++i) cost[i] = inf, dp[i] = -1;
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        cost[start] = 0;
        pq.push({ 0,start });
        while (!pq.empty()) {
            auto [v,from] = pq.top();
            pq.pop();
            if(cost[from] < v) continue;
            for (auto [u,to] : edge[from]) {
                T w = v + u;
                if (w < cost[to]) {
                    cost[to] = w;
                    dp[to] = from;
                    pq.push({ w,to });
                }
            }
        }
        return;
    }
    T get(int idx){
        return cost[idx];
    }
    T get(initializer_list<long long> idx_list){
        int idx = 0;
        auto idx_itr = idx_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            idx += (*idx_itr)*sum[i];
            idx_itr++;
        }
        return get(idx);
    }
    //vertex [start->node1->node2->...->idx]
    vector<int> restore(int idx) {
        vector<int> res = {idx};
        while(dp[idx] != -1) {
            idx = dp[idx];
            res.push_back(idx);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

#line 1 "lib/40-graph/Dijkstra.cpp"
/*
 * @title Dijkstra - 多次元ダイクストラ
 * @docs md/graph/Dijkstra.md
 */
template<class T> class Dijkstra {
    vector<long long> num_list;
    vector<long long> sum;
    int N;
    T inf;
    vector<vector<pair<T,int>>> edge;
    vector<T> cost;
    vector<int> dp;
    void resize(const int N) {
        edge.resize(N);
        cost.resize(N);
        dp.resize(N);
    }
public:
    Dijkstra(int N,T inf):inf(inf),num_list(1,N),sum(1,1),N(N){
        resize(N);
    }
    Dijkstra(initializer_list<long long> size_list,T inf):num_list(size_list),inf(inf),N(1){
        for(long long& e:num_list) N *= e;
        sum.resize(num_list.size(),1);
        for(int i = 0; i < num_list.size(); ++i) {
            for(int j = i + 1; j < num_list.size(); ++j) {
                sum[i] *= num_list[j];
            }
        }
        resize(N);
    }
    void make_edge(int from, int to, T w) {
        if(from < 0 || N <= from || to < 0 || N <= to) return;
        edge[from].push_back({ w,to });
    }
    void make_edge(initializer_list<long long> from_list, initializer_list<long long> to_list, T w) {
        int from = 0, to = 0;
        auto from_itr = from_list.begin(),to_itr = to_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            if(*from_itr < 0 || num_list[i] <= *from_itr || *to_itr < 0 || num_list[i] <= *to_itr) return;
            from += (*from_itr)*sum[i];
            to   += (*to_itr)*sum[i];
            from_itr++;
            to_itr++;
        }
        edge[from].push_back({ w,to });
    }
    void solve(initializer_list<long long> start_list) {
        int start = 0;
        auto start_itr = start_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            start += (*start_itr)*sum[i];
            start_itr++;
        }
        solve(start);
    }
    void solve(int start) {
        for(int i = 0; i < N; ++i) cost[i] = inf, dp[i] = -1;
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        cost[start] = 0;
        pq.push({ 0,start });
        while (!pq.empty()) {
            auto [v,from] = pq.top();
            pq.pop();
            if(cost[from] < v) continue;
            for (auto [u,to] : edge[from]) {
                T w = v + u;
                if (w < cost[to]) {
                    cost[to] = w;
                    dp[to] = from;
                    pq.push({ w,to });
                }
            }
        }
        return;
    }
    T get(int idx){
        return cost[idx];
    }
    T get(initializer_list<long long> idx_list){
        int idx = 0;
        auto idx_itr = idx_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            idx += (*idx_itr)*sum[i];
            idx_itr++;
        }
        return get(idx);
    }
    //vertex [start->node1->node2->...->idx]
    vector<int> restore(int idx) {
        vector<int> res = {idx};
        while(dp[idx] != -1) {
            idx = dp[idx];
            res.push_back(idx);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

Back to top page