提出 #3516953

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<ld> vld;
#define SS(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t){cin >> t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First& first, Rest&...rest){cin >> first;MACRO_VAR_Scan(rest...);}
#define _overload3(_1,_2,_3,name,...) name
#define _REP(i,n) REPI(i,0,n)
#define REPI(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define REP(...) _overload3(__VA_ARGS__,REPI,_REP,)(__VA_ARGS__)
#define ln '\n'

using Weight = ld;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
void add_edge(Graph &g,int a,int b,Weight w=1){g[a].emplace_back(a,b,w);g[b].emplace_back(b,a,w);}
vector<Weight> Dijkstra(const Graph &g,int s) {
    const Weight INF = numeric_limits<Weight>::max()/8;
    using state = tuple<Weight,int>;
    priority_queue<state> q;
    vector<Weight> dist(g.size(),INF);
    dist[s] = 0;
    q.emplace(0,s);
    while (q.size()) {
        Weight d;
        int v;
        tie(d,v) = q.top(); q.pop();
        d *= -1;
        /* if(v == t) return d; */
        if (dist[v]<d) continue;
        for (auto &e : g[v]) {
            if (dist[e.dst] > dist[v] + e.weight) {
                dist[e.dst] = dist[v] + e.weight;
                q.emplace(-dist[e.dst], e.dst);
            }
        }
    }
    return dist;
}

//---------------8<---------------8<---------------8<---------------8<---------------//

int barrier[1010][3];

ld dis(int a, int b) {
  ld res = 0.0;
  res += sqrt(pow(barrier[a][0]-barrier[b][0],2)
            + pow(barrier[a][1]-barrier[b][1],2));
  res -= barrier[a][2] + barrier[b][2];
  if (res < 0) return 0;
  return res;
}

signed main() {

  int start = 0, goal = 1;
  REP(i,2) {
    SS(int,x,y);
    barrier[i][0] = x;
    barrier[i][1] = y;
    barrier[i][2] = 0;
  }

  SS(int,N);
  REP(i,2,N+2) {
    SS(int,x,y,r);
    barrier[i][0] = x;
    barrier[i][1] = y;
    barrier[i][2] = r;
  }

  Graph g(N+2);
  REP(i,N+1) REP(j,i+1,N+2) add_edge(g,i,j,dis(i,j));
  vld v = Dijkstra(g,start);
  cout << setprecision(20) << v[goal] << ln;
}

提出情報

ジャッジ結果