Submission #3625182

---

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
def dijkstra(vnum, vs, edge):
    dist = np.array([np.inf for _ in range(vnum)])
    dist[vs] = 0 
    remain = set(range(vnum))
    Q = []
    heapq.heappush(Q,(0,vs))
    while Q:
        c, vn = heapq.heappop(Q)
        if vn not in remain :
            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 not remain:
            break
    return dist

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)
D = dijkstra(N+2, 0, edge)
print(D[1])

Submission Info

Judge Result