Submission #3625100

---

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
import heapq

xs, ys, xt, yt = flpl()
N = int(input())
xyr = [(xs, ys, 0),(xt, yt, 0)] + [inpl() for _ in range(N)]
X, Y, R = np.array(xyr).T
X, Y, R = np.tile(X, (N+2, 1)), np.tile(Y, (N+2, 1)), np.tile(R, (N+2, 1))
edge = np.maximum(np.zeros((N+2, N+2)), np.sqrt(np.square(X-X.T) +\
                  np.square(Y-Y.T))-(R+R.T)) +\
                  np.diag(np.ones(N+2)*np.inf)

dist = np.array([np.inf for _ in range(N+2)])
dist[0] = 0 
remain = set(range(N+2))
Q = []
heapq.heappush(Q,(0,0))
while Q:
    c, vn = heapq.heappop(Q)
    if vn not in remain or c > dist[c]:
        continue
    remain.remove(vn)
    for j in remain:
        if dist[vn] + edge[vn][j] < dist[j]:
            dist[j] = dist[vn] + edge[vn][j] 
            heapq.heappush(Q,(dist[j],j)) 
    if 1 not in remain:
        break
print(dist[1])

Submission Info

Judge Result