Submission #4033863

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1 << 30;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

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

template<typename T>
struct edge {
    int src, to;
    T cost;

    // to, costで初期化
    edge (int to, T cost) : src(-1), to(to), cost(cost) {}

    // src, to, costで初期化
    edge (int src, int to, T cost) : src(src), to(to), cost(cost) {}

    // toにxを代入？
    edge &operator=(const int &x) {
        to = x;
        return *this;
    }
    
    // edge()でtoを返す？
    operator int() const {return to;}
};

// templates
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<Edges<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/*
 * Dijkstra
 * input: WeightedGraph<T> &g: グラフ
 *        int s: 始点
 * output: vector<T>: sから各要素への最短経路長
 */
template<typename T>
vector<T> dijkstra(WeightedGraph<T> &g, int s) {
    const auto INF = numeric_limits<T>::max();
    vector<T> dist(g.size(), INF);

    using Pi = pair<T, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    dist[s] = 0;
    que.emplace(dist[s], s);
    while(!que.empty()) {
        T cost;
        int idx;
        tie(cost, idx) = que.top();
        que.pop();
        if(dist[idx] < cost) continue;
        for(auto &e : g[idx]) {
            auto next_cost = cost + e.cost;
            if(dist[e.to] <= next_cost) continue;
            dist[e.to] = next_cost;
            que.emplace(dist[e.to], e.to);
        }
    }
    return dist;
}

double distance(double x1, double y1, double x2, double y2) {
  return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  double xs, ys, xt, yt; int n;
  cin >> xs >> ys >> xt >> yt >> n;
  vector<double> x(n), y(n), r(n);
  REP(i, n) {
    cin >> x[i] >> y[i] >> r[i];
  }
  x.pb(xs); y.pb(ys); r.pb(0);
  x.pb(xt); y.pb(yt); r.pb(0);

  WeightedGraph<double> graph(n+2);
  REP(i, n+2) {
    REP(j, n+2) {
      if(i != j) {
        edge<double> e(j, max(0.0, distance(x[i], y[i], x[j], y[j]) - r[i] - r[j]));
        graph[i].pb(e);
      }
    }
  }

  vector<double> dist = dijkstra(graph, n);
  cout << dist[n+1] << endl;
}

Submission Info

Judge Result