Submission #8805695

---

Source Code Expand

from heapq import *
def main():
    import numpy as np
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    inf=float('inf')
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        xy1=np.array([x1,y1])
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            xy2=np.array([x2,y2])
            d_temp=max(0,np.linalg.norm(xy1-xy2)-r1-r2)
            g[i].append([j,d_temp])
            g[j].append([i,d_temp])
    d=[10**10]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append([j,i])
    heapify(h)
    while h:
        i,j=heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heappush(h,[l+i,k])
    print(d[1])
main()

Submission Info

Judge Result