Submission #3607447

---

Source Code Expand

def flpl(): return [float(i) for i in input().split()]
def inpl(): return [int(i) for i in input().split()]
import numpy as np
xs, ys, xt, yt = flpl()
rs,rt = 0, 0
N = int(input())
xyr = [(xs, ys, rs),(xt, yt,rt)] + [inpl() for _ in range(N)]
X, Y, R = np.array(xyr).T
edge = np.zeros((N+2,N+2))
for i in range(N+2):
    for j in range(i+1):
        edge[i][j] = edge[j][i] = max(0, \
            ((X[i]-X[j])**2 + (Y[i]-Y[j])**2)**(1/2) - (R[i]+R[j]))
        inf = float('inf')
dist = np.array([inf for _ in range(N+2)])
dist[0] = 0 
import heapq

decided = [False for _ in range(N+2)]
Q = []
heapq.heappush(Q,(0,0))
for _ in range(N+2):
    while True:
        k = heapq.heappop(Q)
        k = k[1]
        if not decided[k]:
            decided[k] = True
            break
    for j in range(N+2):
        if decided[j]:
            continue
        dist[j] = min(dist[k] + edge[k][j], dist[j])
        heapq.heappush(Q,(dist[j],j)) 
    if decided[1]:
        break
print(dist[1])

Submission Info

Judge Result