test/graph/Dijkstra.test.cpp

View this file on GitHub
Last update: 2023-05-30 04:49:31+09:00
Problem: https://yukicoder.me/problems/no/1065

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1065"
#define ERROR 0.0001
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
#include "../../lib/40-graph/Dijkstra.cpp"
#include "../../lib/70-geometory/Distance.cpp"

int main() {
    int N,M; cin >> N >> M;
    Dijkstra<double> dij(N,1e15);
    int s,t; cin >> s >> t; s--,t--;
    vector<double> p(N),q(N); 
    for(int i = 0; i < N; ++i) {
        cin >> p[i] >> q[i];
    }
    for(int i = 0; i < M; ++i) {
        int u,v; cin >> u >> v;
        u--,v--;
        double cost = Distance<double>::euclid(p[u],q[u],p[v],q[v]);
        dij.make_edge(u,v,cost);
        dij.make_edge(v,u,cost);
    }
    dij.solve(s);
    printf("%.10f\n",dij.get(t));    
    return 0;
}

#line 1 "test/graph/Dijkstra.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1065"
#define ERROR 0.0001
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
#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;
    }
};
#line 1 "lib/70-geometory/Distance.cpp"
/*
 * @title Distance - 距離
 * @docs md/geometory/Distance.md
 */
template<class T> class Distance{
public:
    //Euclidean distance
    inline static constexpr T euclid(const T& x1, const T& y1, const T& x2, const T& y2) {
        return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
    }
    //Chebyshev distance
    inline static constexpr T chebyshev(T x1, T y1, T x2, T y2) {
        return max(abs(x1 - x2),abs(y1 - y2));
    }
    //Manhattan distance
    inline static constexpr T manhattan(T x1, T y1, T x2, T y2) {
        return abs(x1 - x2)+abs(y1 - y2);
    }
    inline static constexpr T between_point_and_line(const T& x,const T& y,const T& x1,const T& y1,const T& x2,const T& y2){
        return abs((y2 - y1)*x+(x1 - x2)*y-(y2-y1)*x1+(x2-x1)*y1)/sqrt((y2 - y1)*(y2 - y1)+(x1 - x2)*(x1 - x2));
    }
};
#line 11 "test/graph/Dijkstra.test.cpp"

int main() {
    int N,M; cin >> N >> M;
    Dijkstra<double> dij(N,1e15);
    int s,t; cin >> s >> t; s--,t--;
    vector<double> p(N),q(N); 
    for(int i = 0; i < N; ++i) {
        cin >> p[i] >> q[i];
    }
    for(int i = 0; i < M; ++i) {
        int u,v; cin >> u >> v;
        u--,v--;
        double cost = Distance<double>::euclid(p[u],q[u],p[v],q[v]);
        dij.make_edge(u,v,cost);
        dij.make_edge(v,u,cost);
    }
    dij.solve(s);
    printf("%.10f\n",dij.get(t));    
    return 0;
}