Submission #4624576

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = 1e9 + 100;
const long long LLINF = 2e18 + 129;
const long long MOD = 1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

struct node{
    int id;
    double cost;

    bool operator<(const node & right) const {
        return cost > right.cost;
    }
};

template<typename T>
bool chmin(T &a, T b){
    if(a > b){
        a = b;
        return true;
    }else{
        return false;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    double sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;

    int n;
    cin >> n;

    vector<double> x(n + 2), y(n + 2), r(n + 2);
    x[0] = sx;
    y[0] = sy;
    r[0] = 0;
    x[n + 1] = gx;
    y[n + 1] = gy;
    r[n + 1] = 0;
    REP(i, 1, n + 1){
        cin >> x[i] >> y[i] >> r[i];
    }

    vector<double> cost(n + 2, DBL_MAX);
    priority_queue<node> que;
    que.push({0, 0.0});
    while(!que.empty()){
        node now = que.top();
        que.pop();
        if(!chmin(cost[now.id], now.cost)){
            continue;
        }
        rep(i, n + 2){
            double ncost = now.cost + max(sqrt(pow(x[i] - x[now.id], 2.0) + pow(y[i] - y[now.id], 2.0)) - r[i] - r[now.id], 0.0);
            if(i != now.id && cost[i] > ncost){
                que.push({i, ncost});
            }
        }
    }

    cout << fixed << setprecision(12) << cost[n + 1] << endl;

    return 0;
}

Submission Info

Judge Result