ARC064 E - Cosmic Rays

問題原文

atcoder.jp

解法

スタートとゴールにも半径０のバリアが張られていると考える。

こういうのはグラフにできないかなと考えるとうれしい。
バリア内は自由に動き回れるので、「バリアの中に入る」ではなく「バリアの中心にたどり着く」ためのコストを考える。
またバリアとバリアの間を移動する時、バリアのそれぞれの中心を結ぶ線分上を移動するのが明らかに最適。
これを考えるとバリア と バリア の間の移動コストは、 「バリア と バリア の距離 - それぞれのバリアの半径」となる。（最低０）

これで各頂点間の移動コスト（距離）が手に入るので、あとはダイクストラ法で最短距離を求めればOK！

実装

import sys
import heapq
my_input = sys.stdin.readline

xs, ys, xt, yt = map(int, my_input().split())
N = int(my_input())
C = [(xs, ys, 0), (xt, yt, 0)]  # 始点と終点も含めとく  
C += [tuple(map(int, my_input().split())) for i in range(N)]

G = [[] for i in range(N+2)]
for i in range(N + 2):
    for j in range(i + 1, N + 2):
        cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
        G[i].append((j, cost))
        G[j].append((i, cost))

dist = dijkstra(G, 0)
print(dist[1])

感想

「実はグラフにできます！」的な問題がすきです。