solution

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

円は綺麗な鎖状に並んだものしか入力されない。 最短経路は折れ線状になるが、その折れ点になりうるのは 円$1, n$の中心と計$2 (n - 1)$点存在する円の交点のみ。 隣接する$2$円の交点は常に$2$つ存在することが保証されているので、その$2$点を繋ぐ線分をgateと呼ぶことにする。 折れ点候補の$2$点$p, q$を取ってきたとき、それらの間を直線で行き来できるのはそれらの間のgate全てを通るとき。 このようにして折れ点候補の間に辺を張り、あとはDijkstraなりWarshall-Floydなりで求める。

注意としては始点と終点を直接つなぐ辺を忘れないこと。 といってもサンプルに入っているので原因不明のWAとなることはないだろう。

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;
}