E - Cosmic Rays AtCoder Regular Contest 064

問題概略
(sx,sy)から(tx,ty)まで移動しようとしています。好きな向きへ速さ1で移動できる。
平面上にN個のバリアが貼ってあり、それぞれ半径が与えられる。
バリアは互いに重なっていることがある。
ゴールへ向かう時、バリアの外にいる時間は最短で何か。

制約
入力はすべて整数である。
−10^9≤xs,ys,xt,yt≤10^9
(xs,ys) ≠ (xt,yt)
1≤N≤1,000
−10^9≤xi,yi≤10^9
1≤ri≤10^9

解法
あるバリアへ向かう時、その中心点へ向かうのが最短である。
スタートとゴールもバリアだとみなしてやれば、バリアからバリアへ辺を貼って最短距離を求めれば良い。
上で貼った辺以外を使って行ける最短経路はない。
なぜなら、最短経路はゴールへ直線か、バリアの恩恵を最大限受けられるあるバリアへの直線だから
O(v^2)のDijkstraでやった

問題の芯
スタート、ゴールを他のものと同じにみなしてやると簡単になる

類題
D - 通勤

 public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        int sx = ni();
        int sy = ni();
        int tx = ni();
        int ty = ni();
        long s = System.currentTimeMillis();
        N = ni();
        double[] x = new double[N + 2];
        double[] y = new double[N + 2];
        double[] r = new double[N + 2];
        x[0] = sx;
        y[0] = sy;
        r[0] = 0;
        x[N + 1] = tx;
        y[N + 1] = ty;
        r[N + 1] = 0;
        for (int i = 1; i < N + 1; i++) {
            x[i] = ni();
            y[i] = ni();
            r[i] = ni();
        }
 
        Dijkstra d = new Dijkstra(0, N + 2);
        for (int i = 0; i < N + 2; i++) {
            for (int j = 0; j < N + 2; j++) {
                if (i == j) continue;
                double cost = u0(Math.sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) - r[i] - r[j]);
                d.addEdge(i, j, cost);
                d.addEdge(j, i, cost);
            }
        }
        double[] dis = d.solve2();
        System.out.println(dis[N + 1]);
    }
 
 
    static class Dijkstra {
        long initValue = LINF;
        Node[] nodes;
        int s, n;
        double[] d;
        double[] d2;
        int prev[]; //最短経路の直前の頂点 -1ならnull
        int prev2[]; //2番目の最短経路の直前の頂点 -1ならnull
 
        Dijkstra(int s, int n) {
            this.s = s;
            this.n = n;
            nodes = new Node[n];
            for (int i = 0; i < n; i++)
                nodes[i] = new Node(i);
            d = new double[n];
            //todo 現状最短経路が複数ある場合に対応できていない
            //todo prev = List<LinkedList>();として複数の直前最短頂点を持とう
            prev = new int[n];
            Arrays.fill(d, initValue);
            Arrays.fill(prev, -1);
            d[s] = 0;
        }

        void addEdge(int f, int t, double c) {
            nodes[f].edges.add(new Edge(t, c));
        }
 
        //O( E ^ 2) 辺が密の時用
        double[] solve2() {
            boolean[] used = new boolean[n];
            double[][] cost = new double[n][n];
            Main.fill(cost, initValue);
 
            for (Node node : nodes) {
                for (Edge edge : node.edges) {
                    int fromId = node.id;
                    int toId = edge.toId;
                    double toCost = edge.toCost;
                    cost[fromId][toId] = toCost;
                }
            }
            while (true) {
                int v = -1;
                //まだ使われていない頂点のうち、距離が最小のものを探す。
                for (int u = 0; u < n; u++)
                    if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
                if (v == -1) break;
                used[v] = true;
                for (int u = 0; u < n; u++) {
                    if (d[u] > d[v] + cost[v][u]) {
                        d[u] = d[v] + cost[v][u];
                        prev[u] = v;
                    }
                }
            }
            return d;
        }
 
        static class Dis implements Comparable<Dis> {
            //現在地点 最短距離
            int p;
            double cos;
 
            Dis(int p, double cost) {
                this.p = p;
                cos = cost;
            }
 
            public int compareTo(Dis d) {
                if (cos != d.cos) {
                    if (cos > d.cos) return 1;
                    else if (cos == d.cos) return 0;
                    else return -1;
                } else {
                    return p - d.p;
                }
            }
        }
 
        static class Node {
            int id;
            List<Edge> edges;
 
            Node(int id) {
                edges = new ArrayList<>();
                this.id = id;
            }
        }
 
        static class Edge {
            int toId;
            double toCost;
 
            Edge(int id, double cost) {
                toId = id;
                toCost = cost;
            }
 
        }
    }