Problem:
 Score : 600 points    Problem Statement On the x y -plane, Snuke is going to travel from the point (x_s, y_s) to the point (x_t, y_t) .
He can move in arbitrary directions with speed 1 .
Here, we will consider him as a point without size.  There are N circular barriers deployed on the plane.
The center and the radius of the i -th barrier are (x_i, y_i) and r_i , respectively.
The barriers may overlap or contain each other.  A point on the plane is exposed to cosmic rays if the point is not within any of the barriers.  Snuke wants to avoid exposure to cosmic rays as much as possible during the travel.
Find the minimum possible duration of time he is exposed to cosmic rays during the travel.      Constraints  All input values are integers.  -10^9 ≤ x_s, y_s, x_t, y_t ≤ 10^9  (x_s, y_s) ≠ (x_t, y_t)  1≤N≤1,000  -10^9 ≤ x_i, y_i ≤ 10^9  1 ≤ r_i ≤ 10^9         Input The input is given from Standard Input in the following format:  x_s  y_s  x_t  y_t  N  x_1  y_1  r_1  x_2  y_2  r_2  :  x_N  y_N  r_N       Output Print the minimum possible duration of time Snuke is exposed to cosmic rays during the travel.
The output is considered correct if the absolute or relative error is at most 10^{-9} .        Sample Input 1 -2 -2 2 2
1
0 0 1      Sample Output 1 3.6568542495  An optimal route is as follows:          Sample Input 2 -2 0 2 0
2
-1 0 2
1 0 2      Sample Output 2 0.0000000000  An optimal route is as follows:          Sample Input 3 4 -2 -2 4
3
0 0 2
4 0 1
0 4 1      Sample Output 3 4.0000000000  An optimal route is as follows:

Solution (Python):
import heapq

def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    
    d = [inf for i in range(n)]
    d[s] = 0

    
    q = [(0,s)]
    heapq.heapify(q)

    
    while q:
        c,p = heapq.heappop(q)

        
        if d[p]<c:
            continue

        
        for cost,to in path[p]:
            
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d

xs,ys,xt,yt = map(int,input().split())
n = int(input())
barrier = [list(map(int, input().split())) for i in range(n)]

barrier = [[xs,ys,0]] + barrier + [[xt,yt,0]]
n+=2

path = [[] for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        length = max(((barrier[i][0]-barrier[j][0])**2 + (barrier[i][1]-barrier[j][1])**2)**0.5-barrier[i][2]-barrier[j][2],0)
        path[i].append([length,j])
        path[j].append([length,i])

d = dijkstra(0,path)

print(d[-1])

Solution (Python):
import math
import heapq

def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    
    d = [inf for i in range(n)]
    d[s] = 0

    
    q = [(0,s)]
    heapq.heapify(q)

    
    while q:
        c,p = heapq.heappop(q)

        
        if d[p]<c:
            continue

        
        for cost,to in path[p]:
            
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d

xs,ys,xt,yt = map(int,input().split())
n = int(input())
barrier = [list(map(int, input().split())) for i in range(n)]

barrier = [[xs,ys,0]] + barrier + [[xt,yt,0]]
n+=2

path = [[] for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        length = max(math.sqrt((barrier[i][0]-barrier[j][0])**2 + (barrier[i][1]-barrier[j][1])**2)-barrier[i][2]-barrier[j][2],0)
        path[i].append([length,j])
        path[j].append([length,i])

d = dijkstra(0,path)

print(d[-1])

Solution (Python):
import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = [(xs, ys, 0)]
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xt, yt, 0))

for i in range(N + 2):
    for j in range(i + 1, N + 2):
        k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
        cost[i][j] = k
        cost[j][i] = k

visit = [0] * (N + 2)
visit[0] = 1
d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0)]
while que:
    dist, v = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[v])
        exit()
    visit[v] = 1
    for w in range(N + 2):
        if visit[w] == 0 and w != v and d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (d[w], w))

Solution (Python):
import math
from heapq import heappush, heappop


def main():
    sx, sy, gx, gy = map(int, input().split())
    N = int(input())
    P = [(sx, sy, 0)] + [(gx, gy, 0)] + \
        [tuple(map(int, input().split())) for _ in range(N)]
    dist = [[0]*(N+2) for _ in range(N+2)]
    for i in range(N+2):
        for j in range(N+2):
            xi, yi, ri = P[i]
            xj, yj, rj = P[j]
            dist[i][j] = max(math.sqrt((xi-xj)**2 + (yi-yj)**2) - (ri+rj), 0.0)
    INF = float("Inf")
    ans = [INF] * (N+2)
    h = [(0.0, 0)]
    while len(h) and ans[1] == INF:
        d, i = heappop(h)
        if ans[i] != INF:
            continue
        ans[i] = d
        for j in range(N+2):
            if ans[j] == INF:
                heappush(h, (d + dist[i][j], j))
    print(ans[1])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
from scipy.spatial.distance import cdist

xs,ys,xt,yt = map(int,input().split())
N = int(input())
XYR = np.empty((N+2,3),dtype=np.int64)
XYR[:2,] = [[xs,ys,0], [xt,yt,0]]

XYR[2:] = np.array([input().split() for _ in range(N)], dtype=np.int64)

XY = XYR[:,:2]
dist = cdist(XY, XY)
R = XYR[:,2]
dist -= R[:,None] + R[None,:]
np.maximum(dist, 0, out = dist)
dist[np.arange(N+2), np.arange(N+2)] = np.inf

graph = csgraph_from_dense(dist, null_value = np.inf)

answer = dijkstra(graph, indices = 0)[1]

print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

xs,ys,xt,yt = map(int,input().split())
N = int(input())
XYR = np.empty((3,N+2),dtype=np.float64)
XYR[:,:2] = [[xs,xt],[ys,yt],[0,0]]

XYR[:,2:] = np.array([input().split() for _ in range(N)], dtype=np.float64).T

X,Y,R = XYR

dist = np.sqrt(np.square(X[:,None] - X[None,:]) + np.square(Y[:,None] - Y[None,:])) 
dist -= R[:,None] + R[None,:]
np.maximum(dist, 0, out = dist)
dist[range(N+2), range(N+2)] = np.inf

graph = csgraph_from_dense(dist, null_value = np.inf)

answer = dijkstra(graph, indices = 0)[1]

print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

xs,ys,xt,yt = map(int,input().split())
N = int(input())
XYR = np.empty((3,N+2),dtype=np.int64)
XYR[:,:2] = [[xs,xt],[ys,yt],[0,0]]

XYR[:,2:] = np.array([input().split() for _ in range(N)], dtype=np.int64).T

X,Y,R = XYR

dist = np.sqrt(np.square(X[:,None] - X[None,:]) + np.square(Y[:,None] - Y[None,:])) 
dist -= R[:,None] + R[None,:]
np.maximum(dist, 0, out = dist)
dist[range(N+2), range(N+2)] = np.inf

graph = csgraph_from_dense(dist, null_value = np.inf)

answer = dijkstra(graph, indices = 0)[1]

print(answer)

Solution (Python):



import sys

input = sys.stdin.readline

inf = float('inf')



def dijkstra(s):
    
    d = [inf] * N
    used = [False] * N
    d[s] = 0
    while True:
        v = -1
        
        for i in range(N):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and (d[i] < d[v]):
                v = i
        if v == -1:
            break
        used[v] = True
        
        for j in range(N):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d


xs, ys, xt, yt = map(int, input().split())
N = int(input())

p = list()
p.append((xs, ys, 0))
p.append((xt, yt, 0))
for _ in range(N):
    p.append(tuple(map(int, input().split())))  

cost = [[0] * (N + 2) for _ in range(N + 2)]



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

cost = tuple(cost)
N += 2

res = dijkstra(0)
print(res[1])

Solution (Python):



import sys

input = sys.stdin.readline

inf = float('inf')



def dijkstra(s):
    
    d = [inf] * N
    used = [False] * N
    d[s] = 0
    while True:
        v = -1
        
        for i in range(N):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and (d[i] < d[v]):
                v = i
        if v == -1:
            break
        used[v] = True
        
        for j in range(N):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d


xs, ys, xt, yt = map(int, input().split())
N = int(input())

p = list()
p.append((xs, ys, 0))
p.append((xt, yt, 0))
for _ in range(N):
    p.append(tuple(map(int, input().split())))  

cost = [[0] * (N + 2) for _ in range(N + 2)]



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

cost = tuple(cost)
N += 2

res = dijkstra(0)
print(res[1])

Solution (Python):
from collections import defaultdict
import heapq
from math import sqrt


import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def calc(b1, b2):
    x1, y1, r1 = b1
    x2, y2, r2 = b2
    d = sqrt((x1-x2)**2+(y1-y2)**2)
    return max(d-(r1+r2), 0)


sx, sy, gx, gy = map(int, input().split())
N = int(input())
barriers = [[sx, sy, 0]] + [list(map(int, input().split()))
                            for _ in range(N)]+[[gx, gy, 0]]

mat = [[0]*(N+2) for _ in range(N+2)]

for row in range(N+2):
    for col in range(row+1, N+2):
        d = calc(barriers[row], barriers[col])
        mat[row][col] = d
        mat[col][row] = d


dist = [float('inf')]*(N+2)
dist[0] = 0


prev = defaultdict(lambda: None)

Q = []

heapq.heappush(Q, (0, 0))

while Q:
    dist_to_node, node = heapq.heappop(Q)
    if dist[node] < dist_to_node:
        continue
    else:
        for v in range(N+2):
            weight = mat[node][v]
            alt = dist_to_node+weight
            if dist[v] > alt:
                dist[v] = alt
                prev[v] = node
                heapq.heappush(Q, (alt, v))
print(dist[-1])

Solution (Python):
def dijkstra(s):
    
    
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
cost = tuple(cost)
n += 2

res = dijkstra(0)
print(res[1])

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
from numpy.linalg import norm
xs, ys, xt, yt = map(int, input().split())
N = int(input())
p=[(xs, ys, 0), (xt, yt, 0)]
edge = [[-1]*(N+2) for _ in range(N+2)]
edge[0][1] = edge[1][0] = norm([xs-xt, ys-yt])
for i in range(N):
    x, y, r = map(int, input().split())
    for j in range(len(p)):
        x1, y1, r1 = p[j]
        edge[i+2][j] = edge[j][i+2] = max(((x1-x)**2+(y1-y)**2)**0.5 - r1 - r,0.0)

    p.append((x, y, r))
G = csgraph_from_dense(edge,null_value=-1)  
print(dijkstra(G,indices=0)[1])

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

xs, ys, xt, yt = map(int, input().split())
n = int(input())

p = [(xs,ys,0),(xt,yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
edge = [[-1]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i+1,n+2):
        edge[i][j] = edge[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0.0)


G = csgraph_from_dense(edge,null_value=-1)
print(dijkstra(G,indices=0)[1])

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

xs, ys, xt, yt = map(int, input().split())
n = int(input())

p = [(xs,ys,0),(xt,yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
edge = [[-1]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i+1,n+2):
        edge[i][j] = edge[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0.0)

G = csgraph_from_dense(edge,null_value=-1)
print(dijkstra(G,indices=0)[1])

Solution (Python):
from heapq import heappop,heappush
import sys
input = sys.stdin.readline
from math import sqrt
xs,ys,xt,yt=map(int,input().split())
N=int(input())
table=[[10**16]*(N+2) for i in range(N+2)]
L=[(xs,ys,0)]
for i in range(N):
    x,y,r=map(int,input().split())
    L.append((x,y,r))
L.append((xt,yt,0))
for i in range(N+2):
    for j in range(i+1,N+2):
        x,y,r=L[i]
        z,w,l=L[j]
        k=max(0,sqrt( abs(x-z)**2 + abs(y-w)**2   )-r-l )
        table[i][j]=k
        table[j][i]=k
H=[]
H.append((0,0))
visit=[0]*(N+2)
visit[0]=1
val=[10**16]*(N+2)
val[0]=0

while H:
    
    cost,pt=heappop(H)
    if val[pt]<cost:
        continue
    if pt==N+1:
        print(val[pt])
        sys.exit()
    visit[pt]=1
    for j in range(N+2):
        if visit[j]==0 and j!=pt and val[j]>table[j][pt]+val[pt]:
            val[j] = table[j][pt] + val[pt]
            heappush(H,(val[j],j))

Solution (Python):
import sys
input=sys.stdin.readline
from heapq import heappush, heappop

def dijkstra(x,Route):
    n=len(Route)
    D=[float('inf')]*n
    D[x]=0
    hq=[(0,x)]
    while hq:
        c,u=heappop(hq)
        if D[u]<c:
            continue
        for v,cost in Route[u]:
            if D[u]+cost<D[v]:
                D[v]=D[u]+cost
                heappush(hq,(D[v],v))
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

Solution (Python):
from heapq import heappush, heappop

def dijkstra(x,Route):
    n=len(Route)
    D=[float('inf')]*n
    D[x]=0
    hq=[(0,x)]
    while hq:
        c,u=heappop(hq)
        if D[u]<c:
            continue
        for v,cost in Route[u]:
            if D[u]+cost<D[v]:
                D[v]=D[u]+cost
                heappush(hq,(D[v],v))
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

Solution (Python):
import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])

Solution (Python):
import math
import heapq
xs,ys,xt,yt=map(int,input().split())
N=int(input())
x=[xs]+[0 for i in range(N)]+[xt]
y=[ys]+[0 for i in range(N)]+[yt]
r=[0]+[0 for i in range(N)]+[0]
for i in range(1,N+1):
    x[i],y[i],r[i]=map(int,input().split())
dist=[10**15 for i in range(N+2)]
dist[0]=0
adjlist=[[0 for i in range(N+2)] for j in range(N+2)]
for i in range(N+2):
    for j in range(N+2):
        if i==j:
            continue
        adjlist[i][j]=max(math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)-r[i]-r[j],0)
q=[]
heapq.heappush(q,(0,0))
while(len(q)>0):
    d,p=heapq.heappop(q)
    if dist[p]<d:
        continue
    for j in range(N+2):
        if p==j:
            continue
        cost=adjlist[p][j]
        if dist[j]>dist[p]+cost:
            dist[j]=dist[p]+cost
            heapq.heappush(q,(dist[j],j))
print(dist[N+1])

Solution (Python):
from math import hypot
def dijkstra(s,n,cost):
    d=[float("inf")]*n
    used=[False]*n
    d[s]=0
    while True:
        v=-1
        for i in range(n):
            if(not used[i])and v==-1:
               v=i
            elif(not used[i])and d[i]<d[v]:
                v = i
        if v==-1:
            break
        used[v]=True
        for j in range(n):
            d[j]=min(d[j],d[v]+cost[v][j])
    return d
xs,ys,xt,yt,n,*t=map(int,open(0).read().split())
e=[(xs,ys,0)]+list(zip(t[::3],t[1::3],t[2::3]))+[(xt,yt,0)]
cost=tuple([float('inf')]*(n+2)for i in range(n+2))
for i,(x,y,z)in enumerate(e):
    for j,(a,b,c)in enumerate(e):
        cost[i][j]=max(0,hypot(x-a,y-b)-z-c)
print(dijkstra(0,n+2,cost)[-1])

Solution (Python):
from math import hypot
def dijkstra(s,n,cost):
    d=[float("inf")]*n
    used=[False]*n
    d[s]=0
    while True:
        v=-1
        for i in range(n):
            if(not used[i])and v==-1:
               v=i
            elif(not used[i])and d[i]<d[v]:
                v = i
        if v==-1:
            break
        used[v]=True
        for j in range(n):
            d[j]=min(d[j],d[v]+cost[v][j])
    return d
xs,ys,xt,yt,n,*t=map(int,open(0).read().split())
e=[(xs,ys,0)]+list(zip(t[::3],t[1::3],t[2::3]))+[(xt,yt,0)]
cost=tuple([float('inf')]*(n+2)for i in range(n+2))
for i,(x,y,z)in enumerate(e):
    for j,(a,b,c)in enumerate(e):
        cost[i][j]=max(0,hypot(x-a,y-b)-z-c)
print(dijkstra(0,n+2,cost)[-1])

Solution (Python):
start_x, start_y, goal_x, goal_y = map(int, input().split())
n = int(input())
info = [(start_x, start_y, 0)] \
       + [tuple(map(int, input().split())) for i in range(n)] \
       + [(goal_x, goal_y, 0)]



graph = [[0]*(n+2) for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        diff_x = info[i][0] - info[j][0]
        diff_y = info[i][1] - info[j][1]
        sum_radius = info[i][2] + info[j][2]
        cost = max(0, ((diff_x)**2 + (diff_y)**2)**(0.5) - sum_radius)
        graph[i][j] = cost
        graph[j][i] = cost
        graph = tuple(graph)



import heapq
distance = [float("inf")]*(n+2)
used = [False]*(n+2)
distance[0] = 0

while True:
    v = -1
    for u in range(n+2):
        if not used[u] and (v == -1 or distance[u] < distance[v]):
            v = u
    if v == -1:
        break
    used[v] = True
    for u in range(n+2):
        distance[u] = min(distance[u], distance[v] + graph[v][u])
            
print(distance[n+1])

Solution (Python):
start_x, start_y, goal_x, goal_y = map(int, input().split())
n = int(input())
info = [(start_x, start_y, 0)] \
       + [tuple(map(int, input().split())) for i in range(n)] \
       + [(goal_x, goal_y, 0)]



graph = [[0]*(n+2) for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        diff_x = info[i][0] - info[j][0]
        diff_y = info[i][1] - info[j][1]
        sum_radius = info[i][2] + info[j][2]
        cost = max(0, ((diff_x)**2 + (diff_y)**2)**(0.5) - sum_radius)
        graph[i][j] = cost
        graph[j][i] = cost
        graph = tuple(graph)



import heapq
distance = [float("inf")]*(n+2)
used = [False]*(n+2)
distance[0] = 0

while True:
    v = -1
    for u in range(n+2):
        if not used[u] and (v == -1 or distance[u] < distance[v]):
            v = u
    if v == -1:
        break
    used[v] = True
    for u in range(n+2):
        distance[u] = min(distance[u], distance[v] + graph[v][u])
            
print(distance[n+1])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from heapq import heappush, heappop


class Node(object):
    def __init__(self, num, x, y, r):
        self.num = num
        self.x = x
        self.y = y
        self.r = r
        

class Graph(object):
    def __init__(self, num):
        self.graph = [[] for _ in range(num)]
        self.nodes = []
        
    
    def calc_edge_len(self, node1, node2):
        dist = sqrt((node1.x - node2.x)**2 + (node1.y - node2.y)**2) - node1.r - node2.r
        if dist <= 0:
            return 0
        else:
            return dist
        
    
    def add_edge(self, node1, node2):
        edge_len = self.calc_edge_len(node1, node2)
        self.graph[node1.num].append((edge_len, node2.num))
        self.graph[node2.num].append((edge_len, node1.num))
    
    def get_graph(self):
        return self.graph


def dijkstra(graph:list, node:int, start:int, goal:int) -> int:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    heap = [(0,start)]
    visited = [False]*node
    
    
    while heap:
        cost, cur_node = heappop(heap)
        
        if visited[cur_node]:
            continue
        
        visited[cur_node] = True
        
        if cur_node == goal:
            return dist[goal]
        
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist[goal]


xs, ys, xt, yt = li()
n = ni()


g = Graph(n+2)
g.nodes.append(Node(0,xs,ys,0))
g.nodes.append(Node(1,xt,yt,0))


for i in range(n):
    x,y,r = li()
    g.nodes.append(Node(i+2,x,y,r))


for i in range(len(g.nodes)):
    for j in range(i+1, len(g.nodes)):
        g.add_edge(g.nodes[i], g.nodes[j])
        
graph = g.get_graph()


dist = dijkstra(graph, n+2, 0,1)

print(dist)

Solution (Python):
import sys
from math import sqrt
def input():
	return sys.stdin.readline()[:-1]

import heapq
class DijkstraMatrix():
	
	
	def __init__(self, matrix, start):
		self.matrix = matrix
		self.start = start
		self.size = len(matrix)

	def solve(self):
		self.dist = [float("inf") for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
				
			for v in range(self.size):
				w = self.matrix[u][v]
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))

			self.cnt += 1

		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
b = [[xs, ys, 0], [xt, yt, 0]] + [list(map(int, input().split())) for _ in range(n)]
d = [[float("inf") for _ in range(n+2)] for _ in range(n+2)]

for i in range(n+2):
	for j in range(n+2):
		if i != j:
			d[i][j] = max(sqrt((b[i][0] - b[j][0])**2 + (b[i][1] - b[j][1])**2) - b[i][2] - b[j][2], 0)

dijkstra = DijkstraMatrix(d, 0)
dijkstra.solve()
print(dijkstra.distance(1))

Solution (Python):
from math import sqrt
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense


def calc_dist(p1,p2):
    return max(0, sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) - (p1[2]+p2[2]))

xs, ys, xg, yg = map(int, input().split())
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
p = [[xs,ys,0], [xg,yg,0]] + p
n += 2
edges = [[float("inf")]*n for i in range(n)]
for i in range(n):
    for j in range(i,n):
        if i == j :continue
        edges[i][j] = edges[j][i] = calc_dist(p[i], p[j])
edges = csgraph_from_dense(edges, null_value=float("inf"))
dist = dijkstra(edges, directed=False, indices=0)
print(dist[1])

Solution (Python):
import math,heapq,sys
input = sys.stdin.readline
xs,ys,xe,ye = map(int,input().split())
cs = [(xs,ys,0), (xe,ye,0)]
N = int(input())
for i in range(N):
    cs.append(tuple(map(int,input().split())))

def calc_cost(i,j):
    if i == j: return float('inf')
    x1,y1,r1 = cs[i]
    x2,y2,r2 = cs[j]
    cost = max(0, math.hypot(x1-x2,y1-y2) - r1 - r2)
    return cost

INF = float('inf')
direct = calc_cost(0,1)
hq = []
for i in range(1,N+2):
    c = calc_cost(0,i)
    if c > direct: continue
    hq.append((c,i))
heapq.heapify(hq)
not_visited = set(range(1,N+2))
cost = [0] + [INF] * (N+1)
while hq:
    c,v = heapq.heappop(hq)
    if v not in not_visited: continue
    if v == 1:
        print(c)
        exit()
    cost[v] = c
    not_visited.remove(v)
    for to in not_visited:
        newcost = calc_cost(v, to)
        if cost[to] <= cost[v] + newcost: continue
        if direct < cost[v] + newcost: continue
        heapq.heappush(hq, (cost[v] + newcost, to))

Solution (Python):
def dijkstra(s):
    
    
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
cost = tuple(cost)
n += 2

res = dijkstra(0)
print(res[1])

Solution (Python):
def dijkstra(s):
    
    
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
cost = tuple(cost)
n += 2

res = dijkstra(0)
print(res[1])

Solution (Python):
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
cost = tuple(cost)
n += 2
s = 0


d = [float("inf")] * n
used = [False] * n
d[s] = 0
    
while True:
    v = -1
    
    for i in range(n):
        if (not used[i]) and (v == -1):
           v = i
        elif (not used[i]) and d[i] < d[v]:
            v = i
    if v == -1:
           break
    used[v] = True
           
    for j in range(n):
           d[j] = min(d[j],d[v]+cost[v][j])
print(d[1])

Solution (Python):
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0


d = [float("inf")] * n
used = [False] * n
d[s] = 0
    
while True:
    v = -1
    
    for i in range(n):
        if (not used[i]) and (v == -1):
           v = i
        elif (not used[i]) and d[i] < d[v]:
            v = i
    if v == -1:
           break
    used[v] = True
           
    for j in range(n):
           d[j] = min(d[j],d[v]+cost[v][j])
print(d[1])

Solution (Python):
from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])

Solution (Python):
import heapq
import math
xs, ys, xt, yt = map(int, input().split())
N = int(input())

Coordinate = {-1: (xs, ys, 0), N:(xt, yt, 0)}
minRadiation = {int(i):10**20 for i in range(-1, N+1)}
ToVisit = {int(i) for i in range(-1, N+1)}
for i in range(N):
    x, y, r = map(int, input().split())
    Coordinate[i] = (x, y, r)

Q = [(0, -1)]
heapq.heapify(Q)
while Q:
    nowRadiation, index = heapq.heappop(Q)
    if index == N:
        print(nowRadiation)
        break
    elif index in ToVisit:
      ToVisit.difference_update({index})
      nowx, nowy, nowr = Coordinate[index]
      for nextIndex in ToVisit:
          nextx, nexty, nextr = Coordinate[nextIndex]
          tempTime = max(0, math.sqrt((nextx-nowx)**2 + (nexty-nowy)**2) - nowr - nextr) + nowRadiation
          if minRadiation[nextIndex] > tempTime:
              minRadiation[nextIndex] = tempTime
              heapq.heappush(Q, (tempTime, nextIndex))