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 sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from itertools import combinations
from math import hypot
input = sys.stdin.readline
sx,sy,gx,gy = map(int,input().split())
n = int(input())
barrier = [list(map(int,input().split())) for i in range(n)]
evv = [(n,n+1,hypot(gx-sx,gy-sy))]
for i in range(n):
  for x1,y1,k in (sx,sy,n),(gx,gy,n+1):
    b1 = barrier[i]
    x2,y2,r = b1[0],b1[1],b1[2]
    dist = max(hypot(x2-x1,y2-y1)-r,0)
    evv.append((i,k,dist))
for i,j in combinations(range(n),2):
  b1 = barrier[i]
  b2 = barrier[j]
  x1,y1,r1 = b1[0],b1[1],b1[2]
  x2,y2,r2 = b2[0],b2[1],b2[2]
  dist = max(hypot(x2-x1,y2-y1)-(r1+r2),0)
  evv.append((i,j,dist))
v1,v2,edge = zip(*evv)
csr = csr_matrix((edge,(v1,v2)),shape = (n+2,n+2))
print(dijkstra(csr, directed = False,indices = n)[n+1])

Solution (Python):
import heapq


def dijkstra(adj: list, start, goal=None):
    """adj:隣接行列"""
    num = len(adj)          
    dist = [float('inf') for i in range(num)]  
    prev = [float('inf') for i in range(num)]  
    dist[start] = 0
    
    q = []
    heapq.heappush(q, (0, start))  
    while q:
        prov_cost, src = heapq.heappop(q)  
        
        if dist[src] < prov_cost:
            continue
        
        for dest in range(num):
            cost = adj[src][dest]
            if cost != float('inf') and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost  
                
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src                      
    return dist


INF = float('inf')
xs, ys, xt, yt = map(int, input().split())
n = int(input())
n += 2
li = [None] * n
li[0] = (xs, ys, 0)
li[n - 1] = (xt, yt, 0)
for i in range(n - 2):
    x, y, r = map(int, input().split())
    li[i + 1] = (x, y, r)
mat = [[INF] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
    for j in range(i + 1, n):
        x1, y1, r1 = li[i]
        x2, y2, r2 = li[j]
        d = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** .5
        res = max(d - r1 - r2, 0)
        mat[i][j] = res
        mat[j][i] = res
d = dijkstra(mat, 0)
print(d[n - 1])

Solution (Python):
import heapq

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

N = int(input())

xyr = []
xyr.append([xs,ys,0])



for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0
used = [False] * (N+2)

while True:

    v = -1

    
    for i in range(N+2):
        if not used[i] and (v == -1 or ans[v] > ans[i]):
            v = i
    
    if v == -1:
        break
    
    used[v] = True
    for i in range(N+2):
        ans[i] = min(ans[i] , ans[v] + d[v][i])


print (ans[-1])

Solution (Python):
def examC():
    N, x  = LI()
    A = LI()
    ans = 0
    cur = A[0]
    if A[0]>x:
        ans += A[0]-x
        cur = x
    for i in range(1,N):
        if cur+A[i]<=x:
            cur = A[i]
            continue
        ans += cur+A[i]-x
        cur = A[i]-(cur+A[i]-x)
    print(ans)
    return

def examD():
    S = SI()
    return

def dijkstra(edge_adj, node, start):
    
    dist = [inf] * node
    used = [False] * node
    dist[start] = 0
    while True:
        v = -1
        for i in range(node):
            if not used[i] and (v == -1 or dist[v] > dist[i]):
                v = i
        if v == -1:
            break
        used[v] = True
        for i in range(node):
            if dist[i] > dist[v] + edge_adj[v][i]:
                dist[i] = dist[v] + edge_adj[v][i]

    return dist
def examE():
    xs,ys,xg,yg = LI()
    N = I()
    XYR = [[]for _ in range(N)]
    for i in range(N):
        XYR[i] = LI()
    XYR.append([xs,ys,0])
    XYR.append([xg,yg,0])
    V = [[0]*(N+2) for _ in range(N+2)]
    for i in range(N+2):
        for j in range(i+1,N+2):
            s = XYR[i]; t = XYR[j]
            cur = ((s[0]-t[0])**2 + (s[1]-t[1])**2)**0.5 - (s[2]+t[2])
            V[i][j] = max(0,cur)
            V[j][i] = max(0,cur)
    D = dijkstra(V,N+2,N)

    ans = D[-1]
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examE()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    CR=[None]*(n+2) 
    CR[0]=(xs+ys*1j,0)
    CR[n+1]=(xt+yt*1j,0)
    for i in range(1,n+1):
        x,y,r=map(int,input().split())
        CR[i]=(x+y*1j,r)


    
    n+=2
    E=[[] for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        c0,r0=CR[i]
        c1,r1=CR[j]
        d=max(0,abs(c0-c1)-r0-r1)
        E[i].append((j,d))
        E[j].append((i,d))

    
    dist=[INF]*n
    dist[0]=0
    used=[0]*n
    for _ in range(n-1):
        v=min((dist[v],v) for v in range(n) if(not used[v]))[1]
        used[v]=1
        for nv,w in E[v]:
            if(dist[nv]>dist[v]+w):
                dist[nv]=dist[v]+w

    print(dist[-1])
resolve()

Solution (Python):
def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    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]
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            d_temp=max(0,((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2)
            g[i].append((j,d_temp))
            g[j].append((i,d_temp))
    d=[0]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append((j,i))
    heapq.heapify(h)
    while h:
        i,j=heapq.heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heapq.heappush(h,(l+i,k))
    print(d[1])
main()

Solution (Python):
import math
import heapq as hp
import sys
input = sys.stdin.readline

sx, sy, tx, ty = map(int, input().split())
N = int(input())
XYR = [list(map(int, input().split())) for _ in range(N)]
INF = 10**14

graph = [[] for _ in range(N+2)]
for i in range(N-1):
    for j in range(1, N):
        x1, y1, r1 = XYR[i]
        x2, y2, r2 = XYR[j]
        d = max(0, math.sqrt((x1-x2)**2+(y1-y2)**2)-r1-r2)
        graph[i].append((d, j))
        graph[j].append((d, i))

for i in range(N):
    x, y, r = XYR[i]
    graph[N].append((max(0, math.sqrt((x-sx)**2+(y-sy)**2)-r), i))
    graph[i].append((max(0, math.sqrt((x-tx)**2+(y-ty)**2)-r), N+1))

graph[N].append((math.sqrt((tx-sx)**2+(ty-sy)**2), N+1))

D = [INF for _ in range(N+2)] 
D[N] = 0 
q = [] 
hp.heappush(q, (0, N))

while q:
    nd, np = hp.heappop(q) 
    if D[np] < nd: 
        continue
    for d, p in graph[np]:
        if D[p] > D[np] + d: 
            D[p] = D[np] + d
            hp.heappush(q, (D[p], p))

print(D[N+1])

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

xs, ys, xt, yt = map(int, input().split())
N = int(input())
xyr = [[int(i) for i in input().split()] for _ in range(N)]

cost = [0] * N
h = []

def dist(x, y) :
    return sqrt(x ** 2 + y ** 2)

for i, (x, y, r) in enumerate(xyr) :
    d = max(0, dist(xs-x, ys-y) - r)
    heappush(h, (d, i))
    cost[i] = d
 
while h :
    dc, i = heappop(h)
    if cost[i] < dc :
        continue
        
    xc, yc, rc = xyr[i]
    
    for i, (x, y, r) in enumerate(xyr) :
        d = dc + max(0, dist(xc-x, yc-y) - rc - r)
        if d < cost[i] :
            heappush(h, (d, i))
            cost[i] = d
            
ret = sqrt((xs-xt) ** 2 + (ys-yt)**2)
for i, (x, y, r) in enumerate(xyr) :
    ret = min(ret, cost[i] + max(0, dist(xt-x, yt-y) - r))
    
print(ret)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


sx, sy, gx, gy = LI()
n = I()
circles = [[sx, sy, 0]] + LIR(n) + [[gx, gy, 0]]
G = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n + 2):
    for j in range(i + 1, n + 2):
        G[i][j] = G[j][i] = \
        max(0, ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5 - circles[i][2] - circles[j][2])


def dijkstra(graph, start=0):
    que = [(0, start)]
    dist = [INF] * (n + 2)
    dist[start] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for v, c in enumerate(graph[u]):
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(que, (dist[u] + c, v))
    return dist


print(dijkstra(G, start=0)[-1])

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


def dijkstra(adj, start):
    
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        
        
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [(xs, ys, 0), (xt, yt, 0)]
    for _ in range(N):
        br.append(tuple(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


if __name__ == '__main__':
    main()

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

Xs,Ys,Xg,Yg=map(int,input().split())
N=int(input())
L=[]
L.append([Xs,Ys,0])
for i in range(N):
    x,y,r=map(int,input().split())
    L.append([x,y,r])
L.append([Xg,Yg,0])
cost=[[-1 for i in range(N+2)]for j in range(N+2)]
for i in range(N+2):
    for j in range(i,N+2):
        cost[i][j]=max(0,((L[i][0]-L[j][0])**2+(L[i][1]-L[j][1])**2)**0.5-L[i][2]-L[j][2])
        cost[j][i]=cost[i][j]



def jdijkstra(s,n,w,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


ans=jdijkstra(0,N+2,(N+2)**2,cost)
print(ans[-1])

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

xs, ys, xt, yt = list(map(int, input().split()))
N = int(input())
circle = [(xs, ys, 0)]
for i in range(N):
	circle.append(tuple(map(int, input().split())))
circle.append((xt, yt, 0))

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

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

dist = [10**13]*(N + 2)
dist[0] = 0

node_list = []
heapq.heappush(node_list, (0, 0))
while len(node_list) > 0:
	node = heapq.heappop(node_list)
	if dist[node[1]] == node[0]:
		for i in range(N + 2):
			if i != node[1] and dist[i] > node[0] + graph[node[1]][i]:
				dist[i] = node[0] + graph[node[1]][i]
				heapq.heappush(node_list, (dist[i], i))

print(dist[-1])

Solution (Python):

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, dijkstra



import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[(xs,ys,0),(xt,yt,0)]
data=[[-1]*(n+2) for i in range(n+2)]
for i in range(n):
    xyr.append(tuple(map(int,input().split())))


for i in range(n+1):
    for j in range(i+1,n+2):
        x0 = xyr[i][0]
        y0 = xyr[i][1]
        r0 = xyr[i][2]
        x1 = xyr[j][0]
        y1 = xyr[j][1]
        r1 = xyr[j][2]
        data[i][j]=max(((x0-x1)**2+(y0-y1)**2)**.5-r0-r1,0)

G = csgraph_from_dense(data, null_value=-1)


d = dijkstra(G, indices=0, directed=False)
print(d[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):
a,b,c,d=map(int,input().split())
n=int(input())
s=[[a,b,0]]+[list(map(int,input().split()))for i in range(n)]+[[c,d,0]]
c=[[0]*(n+2)for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        c[i][j]=c[j][i]=max(0,((s[i][0]-s[j][0])**2+(s[i][1]-s[j][1])**2)**0.5-s[i][2]-s[j][2])
c=tuple(c)
n+=2
a=[float("INF")]*(n)
b=[1]*(n)
a[0]=0
while 1:
    v=-1
    for i in range(n):
        if v==-1 and b[i]:
            v=i
        elif b[i] and a[i]<a[v]:
            v=i
    if v==-1:
        break
    b[v]=0
    for j in range(n):
        a[j]=min(a[j],a[v]+c[v][j])
print(a[-1])

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

def dijkstra(edge_adj: list, node: int, start: int) -> list:
    
    inf = 3 * 10 ** 9
    dist = [inf] * node
    used = [False] * node

    dist[start] = 0
    while True:
        v = -1
        for i in range(node):
            if not used[i] and (v == -1 or dist[v] > dist[i]):
                v = i

        if v == -1:
            break

        used[v] = True
        for i in range(node):
            if dist[i] > dist[v] + edge_adj[v][i]:
                dist[i] = dist[v] + edge_adj[v][i]

    return dist
    

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    circles.append(tuple(map(int, input().split())))
n += 2

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


dist = dijkstra(edges, n, 0)

print(dist[1])

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

def dijkstra(edge_adj: list, node: int, start: int) -> list:
    
    inf = 3 * 10 ** 9
    dist = [inf] * node
    used = [False] * node

    dist[start] = 0
    while True:
        v = -1
        for i in range(node):
            if not used[i] and (v == -1 or dist[v] > dist[i]):
                v = i

        if v == -1:
            break

        used[v] = True
        for i in range(node):
            if dist[i] > dist[v] + edge_adj[v][i]:
                dist[i] = dist[v] + edge_adj[v][i]

    return dist
    

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    circles.append(tuple(map(int, input().split())))
n += 2

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


dist = dijkstra(edges, n, 0)

print(dist[1])

Solution (Python):
from collections import deque

sX, sY, eX, eY = map(int, input().split())

N = int(input())
circles = [(sX, sY, 0)]
for _ in range(N):
    x, y, r = map(int, input().split())
    circles.append((x, y, r))
circles.append((eX, eY, 0))

edges = [[float('inf')] * (N + 2) for _ in range(N + 2)]

for i, (x, y, r) in enumerate(circles):
    for j, (u, v, s) in enumerate(circles):
        d = max(0, ((x - u)**2 + (y - v)**2)**0.5 - (r + s))
        edges[i][j] = d

minDist = [float('inf')] * (N + 2)
confilm = [False] * (N + 2)
minDist[0] = 0
for _ in range(N + 2):
    minNode = (-1, float('inf'))
    for to in range(N + 2):
        if not confilm[to] and minDist[to] < minNode[1]:
            minNode = (to, minDist[to])
    confilm[minNode[0]] = True
    for to in range(N + 2):
        minDist[to] = min(minDist[to], minDist[minNode[0]] + edges[minNode[0]][to])

print(minDist[-1])

Solution (Python):
from math import sqrt
from collections import defaultdict as dd
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    while not t in vis:
      v = -1
      for i in range(self.n):
        if (not i in vis) and (v == -1):
          v = i
        elif (not i in vis) and d[i] < d[v]:
          v = i
      if v == -1:
        break
      vis.add(v)
      for p in self.e[v]:
        d[p[0]] = min(d[p[0]], d[v] + p[1])
    return d[t]
def distance(u1, v1, r1, u2, v2, r2):
  dis = sqrt(((u1 - u2) ** 2) + ((v1 - v2) ** 2))
  return max(dis - r1 - r2, 0)
sx, sy, tx, ty = map(int, input().split())
N = int(input())
c = [list(map(int, input().split())) for _ in range(N)]
c.append([sx, sy, 0])
c.append([tx, ty, 0])
e = dd(list)
for i in range(N + 1):
  for j in range(N + 2):
    if i == j: continue
    if j == N: continue
    e[i + 1].append([j + 1, distance(c[i][0], c[i][1], c[i][2], c[j][0], c[j][1], c[j][2])])
d = dijkstra(N + 2, e)
print(d.path(N + 1, N + 2))

Solution (Python):
sX, sY, eX, eY = map(int, input().split())
N = int(input())

circles = [(sX, sY, 0)]
for _ in range(N):
    cx, cy, r = map(int, input().split())
    circles.append((cx, cy, r))
circles.append((eX, eY, 0))

edges = [[float('inf')] * (N + 2) for _ in range(N + 2)]

for i, (cx1, cy1, r1) in enumerate(circles):
    for j, (cx2, cy2, r2) in enumerate(circles):
        cDist = ((cx1 - cx2)**2 + (cy1 - cy2)**2)**0.5
        dist = max(0, cDist - r1 - r2)

        edges[i][j] = dist
        edges[j][i] = dist

minDist = [float('inf')] * (N + 2)
minDist[0] = 0
confilm = [False] * (N + 2)

for _ in range(N + 2):
    md = float('inf')
    minNode = -1
    for n in range(N + 2):
        if not confilm[n] and md > minDist[n]:
            minNode = n
            md = minDist[n]
    confilm[minNode] = True
    for to in range(N + 2):
        minDist[to] = min(minDist[to], minDist[minNode] + edges[minNode][to])

print(minDist[-1])

Solution (Python):
import sys
input = sys.stdin.readline
 
from heapq import heappop,heappush
import math
 
xs,ys,xt,yt = map(int,input().split())
n = int(input())
 
v = [[xs,ys,0]]
for _ in range(n):
    x,y,r = map(int,input().split())
    v.append([x,y,r])
v.append([xt,yt,0])
 
def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])

edges=[[0]*(n+2) for _ in range(n+2)]
for i in range(n+2):
    for j in range(i+1,n+2):
        edges[i][j] = dd(v[i],v[j])
        edges[j][i] = dd(v[i],v[j])

def dijkstra(s,n,edges):
    
    
    d = [float('inf') for _ in range(n)]
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d

ans = dijkstra(0,n+2,edges)
print(ans[n+1])

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

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))
        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

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


xs, ys, xg, yg = list(map(int, input().split()))
xyr = []
xyr.append([xs, ys, 0])
N = int(input())

for i in range(N):
    xyr.append(list(map(int, input().split())))
xyr.append([xg, yg, 0])

g_a = Graph()
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        R = ((xyr[i][0] - xyr[j][0]) * (xyr[i][0] - xyr[j][0]) + (xyr[i][1] - xyr[j][1]) * (xyr[i][1] - xyr[j][1]))
        R = R ** 0.5
        if R > xyr[i][2] + xyr[j][2]:
            r = R - xyr[i][2] - xyr[j][2]
        else:
            r = 0
        g_a.add_edge(i, j, r)
        g_a.add_edge(j, i, r)

d_a = Dijkstra(g_a, 0)
print(d_a.s_d(N + 1))

Solution (Python):
from heapq import *

xs, ys, xt, yt = [int(_) for _ in input().split()]
N = int(input())
XYR = [[xs, ys, 0]] + [[int(_) for _ in input().split()]
                       for _ in range(N)] + [[xt, yt, 0]]
G = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        G[i][j] = G[j][i] = max(
            ((XYR[i][0] - XYR[j][0])**2 +
             (XYR[i][1] - XYR[j][1])**2)**0.5 - XYR[i][2] - XYR[j][2], 0)


def dijkstra(V, G, start):
    INF = float('inf')
    D = [INF for _ in range(V)]
    D[start] = 0
    H = [(0, start)]
    while H:
        du, u = heappop(H)
        if D[u] < du:
            continue
        for v, d in enumerate(G[u]):
            if D[v] > du + d:
                D[v] = du + d
                heappush(H, (D[v], v))
    return D


D = dijkstra(N + 2, G, 0)
print(D[-1])

Solution (Python):
import sys
import heapq as h
stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def dist(p,q):
  px,py,pr = p
  qx,qy,qr = q
  d = ((px-qx)**2 + (py-qy)**2)**.5
  return max(d-(pr+qr),0)
  
  

xs,ys,xt,yt = nm()
n = ni()
pl = [(xs,ys,0)] + [tuple(nm()) for _ in range(n)] + [(xt,yt,0)]
gr = [dict() for _ in range(n+2)]
for i in range(n+1):
  for j in range(i+1,n+2):
    gr[i][j] = dist(pl[i],pl[j])
    gr[j][i] = gr[i][j]

dis = [float("inf")]*(n+2)
q = [(0,0)]
while q:
  d,v = h.heappop(q)
  if dis[v] <= d:
    continue
  dis[v] = d
  for x in gr[v]:
    if dis[x] > dis[v]+gr[v][x]:
      h.heappush(q,(dis[v]+gr[v][x],x))
print(dis[-1])

Solution (Python):
import math
import os
import sys

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

SX, SY, TX, TY = list(map(int, sys.stdin.readline().split()))
N = int(sys.stdin.readline())
X, Y, R = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

X = np.concatenate([X, [SX, TX]])
Y = np.concatenate([Y, [SY, TY]])
R = np.concatenate([R, [0, 0]])

S = N
T = N + 1
XI, XJ = np.meshgrid(X, X)
YI, YJ = np.meshgrid(Y, Y)
RI, RJ = np.meshgrid(R, R)
V, U = np.meshgrid(np.arange(N + 2), np.arange(N + 2))
D = np.maximum(0, np.sqrt(np.power(XI - XJ, 2) + np.power(YI - YJ, 2)) - RI - RJ)

ret = dijkstra(csr_matrix((D.ravel(), (U.ravel(), V.ravel()))), directed=False, indices=S)
print(ret[T])

Solution (Python):
import heapq
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

SX, SY, TX, TY = list(map(int, sys.stdin.readline().split()))
N = int(sys.stdin.readline())
XYR = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

S = N
T = N + 1
XYR.append([SX, SY, 0])
XYR.append([TX, TY, 0])
graph = [[] for _ in range(N + 2)]
for i, (xi, yi, ri) in enumerate(XYR):
    for j, (xj, yj, rj) in enumerate(XYR):
        if i == j:
            continue
        d = math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - ri - rj
        graph[i].append((max(0, d), j))

heap = [(0, S)]
heapq.heapify(heap)
dist = [IINF] * (N + 2)
while heap:
    w, v = heapq.heappop(heap)
    if w > dist[v]:
        continue
    for dw, u in graph[v]:
        if w + dw < dist[u]:
            dist[u] = w + dw
            heapq.heappush(heap, (w + dw, u))
print(dist[T])

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 collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()

    return


def B():
    n = I()

    return


def C():
    def dist(a,b):
        xa,ya,ra = a
        xb,yb,rb = b
        return max(0, ((xa-xb)**2+(ya-yb)**2)**0.5-(ra+rb))

    xs,ys,xt,yt = LI()
    n = I()
    p = LIR(n)
    v = [[] for i in range(n+2)]
    a = (xs,ys,0)
    b = (xt,yt,0)
    d = dist(a,b)
    v[0].append((n+1, d))
    for i in range(n):
        d = dist(a,p[i])
        v[0].append((i+1,d))
        d = dist(p[i],b)
        v[i+1].append((n+1,d))
        for j in range(i+1,n):
            d = dist(p[i],p[j])
            v[i+1].append((j+1,d))
            v[j+1].append((i+1,d))
    d = [float("inf")]*(n+2)
    q = [(0,0)]
    d[0] = 0
    while q:
        dx,x = heappop(q)
        if x > n:
            print(d[x])
            return
        if d[x] < dx:
            continue
        for y,w in v[x]:
            nd = dx+w
            if nd < d[y]:
                d[y] = nd
                heappush(q,(nd,y))
    return


def D():
    n = I()

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

Solution (Python):
xs,ys,xt,yt = map(int,input().split())
N = int(input())
XYR = [list(map(int,input().split())) for _ in [0]*N]
XYR.append([xs,ys,0])
XYR.append([xt,yt,0])

E = [{} for _ in [0]*(N+2)]
for i in range(N+2):
    for j in range(N+2):
        if j==i : continue
        dx = XYR[i][0]-XYR[j][0]
        dy = XYR[i][1]-XYR[j][1]
        r2 = XYR[i][2]+XYR[j][2]
        E[i][j] = max(0,(dx**2+dy**2)**0.5 - r2)

import heapq
def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d

print(Dijkstra(N+2,E,N)[-1])