solution

がんばって実装。$O(N^3)$。

implementation

#include <cmath>
#include <cstdio>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

const double eps = 1e-6;
double sq(double x) { return pow(x, 2); }

struct point { double y, x; };
struct circle { point p; double r; };
struct segment { point s, t; };

point operator + (point a, point b) { return (point) { a.y + b.y, a.x + b.x }; }
point operator - (point a, point b) { return (point) { a.y - b.y, a.x - b.x }; }
point operator * (point a, double b) { return (point) { a.y * b, a.x * b }; }
point operator / (point a, double b) { return (point) { a.y / b, a.x / b }; }
bool operator < (point a, point b) { return make_pair(a.y, a.x) < make_pair(b.y, b.x); }
double distance(point a, point b) { return sqrt(sq(a.y - b.y) + sq(a.x - b.x)); }
double   dot(point a, point b) { return a.x * b.x + a.y * b.y; }
double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
int ccw(point a, point b, point c) { double z = cross(b - a, c - a); return z > eps ? 1 : z < - eps ? -1 : 0; }
bool does_intersect(segment const & a, segment const & b){
return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) <= 0 and
ccw(b.s, b.t, a.s) * ccw(b.s, b.t, a.t) <= 0;
}

segment intersections(circle c1, circle c2) {
double a = c1.r;
double b = c2.r;
double c = distance(c1.p, c2.p);
double x = (sq(a) - sq(b) + sq(c)) / (2 * c);
double y = sqrt(sq(a) - sq(x));
point e = (c2.p - c1.p) / c;
point center = e * x + c1.p;
point f = { e.x, - e.y };
point p = center + f * y;
point q = center - f * y;
return { p, q };
}

int main() {
while (true) {
// input
int n; scanf("%d", &n);
if (n == 0) break;
vector<circle> c(n);
repeat (i, n) {
scanf("%lf%lf%lf", &c[i].p.x, &c[i].p.y, &c[i].r);
}
// solve
vector<segment> gate(n - 1);
repeat (i, n - 1) {
gate[i] = intersections(c[i], c[i+1]);
}
vector<point> p(2 * n);
const int src = 2 * (n - 1);
const int dst = 2 * (n - 1) + 1;
repeat (i, n - 1) {
p[2 * i    ] = gate[i].s;
p[2 * i + 1] = gate[i].t;
}
p[src] = c[0].p;
p[dst] = c[n - 1].p;
vector<vector<pair<int, double> > > g(2 * n);
auto is_valid = [&](segment a, int l, int r) { // [l, r)
repeat_from (i, l, r) {
if (not does_intersect(a, gate[i])) return false;
}
return true;
};
repeat (l, n - 1) {
for (int i : { 2 * l, 2 * l + 1 }) {
repeat_from (r, l + 1, n - 1) { // [l, r]
for (int j : { 2 * r, 2 * r + 1 }) {
if (is_valid((segment) { p[i], p[j] }, l + 1, r)) {
g[i].emplace_back(j, distance(p[i], p[j]));
}
}
}
if (is_valid((segment) { p[src], p[i] }, 0, l)) {
g[src].emplace_back(i, distance(p[src], p[i]));
}
if (is_valid((segment) { p[i], p[dst] }, l + 1, n - 1)) {
g[i].emplace_back(dst, distance(p[i], p[dst]));
}
}
}
if (is_valid((segment) { p[src], p[dst] }, 0, n - 1)) {
g[src].emplace_back(dst, distance(p[src], p[dst]));
}
auto dist = vectors(2 * n, 2 * n, INFINITY);
repeat (i, 2 * n) {
dist[i][i] = 0;
for (auto e : g[i]) {
int j; double d; tie(j, d) = e;
dist[i][j] = d;
}
}
repeat (k, 2 * n) repeat (i, 2 * n) repeat (j, 2 * n) { // Warshall-Floyd
setmin(dist[i][j], dist[i][k] + dist[k][j]);
}
printf("%.10lf\n", dist[src][dst]);
}
return 0;
}