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 math
xs,ys,xg,yg= map(int,input().split())
n = int(input())
c = [[-1,xs,ys,0]]
for i in range(n):
    x,y,r = map(int,input().split())
    c.append([max(math.sqrt(abs(xs-x)**2+abs(ys-y)**2)-r,0),x,y,r])
dp  = [float("inf")]*(n+1)
dp[0] = 0
used = [0]*(n+1)
for i in range(n+1):
    a = float("inf");b=-1
    for j in range(n+1):
        if used[j]:continue
        if a > dp[j]:
            a = dp[j];b = j
    used[b] = 1
    g = b
    _,x,y,r = c[b]
    for j in range(n+1):
        if used[j]:
            continue
        _,x2,y2,r2 = c[j]
        ima = dp[g]+max(0,math.sqrt(abs(x2-x)**2+abs(y2-y)**2)-r-r2)
        if ima < dp[j]:
            dp[j] = ima
ans = float("inf")
for i in range(n+1):
    _,x,y,r = c[i]
    ans = min(dp[i]+max(0,math.sqrt(abs(xg-x)**2+abs(yg-y)**2)-r),ans)
print(ans)

Solution (Python):
from heapq import heappush,heappop 
from math import sqrt
inf=float("inf")

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

q=[]
l=[(xs,ys,0),(xt,yt,0)]+[tuple(map(int,input().split())) for _ in range(n)]

sizeV=len(l)
rests=set(range(sizeV))
cost=[inf]*sizeV
cost[0]=0
heappush(q,(0,0))

while q:
  c1,i=heappop(q)
  if c1>cost[i]:continue

  rests.remove(i)
  if not rests:break

  xi,yi,ri=l[i]
  for j in rests:
    xj,yj,rj=l[j]
    d=max(0.0,sqrt((xj-xi)**2+(yj-yi)**2)-ri-rj)
    c2=c1+d
    if c2<cost[j]:
      cost[j]=c2
      heappush(q,(c2,j))

print(cost[1])

Solution (Python):
from collections import defaultdict
xs,ys,xt,yt=map(int,input().split())
P=[]
inf=float("inf")
P.append((xs,ys,0))
P.append((xt,yt,0))
N=int(input())
for i in range(N):
  x,y,r=map(int,input().split())
  P.append((x,y,r))

G=defaultdict(int)
for i in range(N+2):
  for j in range(N+2):
      x1,y1,r1,x2,y2,r2=P[i][0],P[i][1],P[i][2],P[j][0],P[j][1],P[j][2]
      d=((x1-x2)**2+(y1-y2)**2)**(1/2)
      G[(i,j)]=max(0,d-r1-r2)

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

Solution (Python):
def flpl(): return [float(i) for i in input().split()]
def inpl(): return [int(i) for i in input().split()]
import heapq
def dijkstra(vnum, vs):
    dist = [float('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:
            evnj = edge(vn, j)
            if dist[vn] + evnj < dist[j]:
                dist[j] = dist[vn] + evnj 
                heapq.heappush(Q,(dist[j],j)) 
        if not remain:
            break
    return dist
def edge(s, t):
    return max(((X[s] - X[t])**2 + (Y[s] - Y[t])**2)**(1/2) -(R[s]+R[t]), 0)

xs, ys, xt, yt = flpl()
N = int(input())
xyr = [(xs, ys, 0),(xt, yt, 0)] + [inpl() for _ in range(N)]
X, Y, R = list(map(list, zip(*xyr)))
D = dijkstra(N+2, 0)
print(D[1])

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

INF = float('inf')


def Dijkstra(barriers, vSt):
    numV = len(barriers)
    rests = set(range(numV))
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))

    while PQ:
        c, vNow = heappop(PQ)
        if c > costs[vNow]: continue

        rests.remove(vNow)
        if not rests: break

        costNow = c
        xi, yi, ri = barriers[vNow]
        for v2 in rests:
            xj, yj, rj = barriers[v2]
            wt = sqrt((xj - xi) ** 2 + (yj - yi) ** 2) - ri - rj
            if wt < 0: wt = 0
            c2 = costNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))

    return costs


xs, ys, xt, yt = map(int, input().split())
N = int(input())
barriers = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for _ in range(N)]

costs = Dijkstra(barriers, 0)
print(costs[1])

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

INF = 10 ** 20

xs, ys, xt, yt = map(int, input().split())
N = int(input())
X = np.zeros((1, N + 2), dtype=np.float64)
Y = np.zeros((1, N + 2), dtype=np.float64)
R = np.zeros((1, N + 2), dtype=np.float64)

X[0][0] = xs
Y[0][0] = ys
X[0][N + 1] = xt
Y[0][N + 1] = yt

for i in range(N):
    X[0][i + 1], Y[0][i + 1], R[0][i + 1] = map(int, input().split())


G = np.maximum(np.sqrt(np.square(X - X.T) + np.square(Y - Y.T)) - (R + R.T),
               np.zeros((N + 2, N + 2), dtype=np.float64))

G += np.diag(np.ones(N + 2, dtype=np.float64) * np.inf)

G = csgraph_from_dense(G, null_value=np.inf)
print(dijkstra(G, indices=0)[-1])

Solution (Python):
import heapq

xs, ys, xt, yt = map(int, input().split())
N = int(input())
XYR = [list(map(int, input().split())) for i in range(N)]
XYR.append([xs, ys, 0])
XYR.append([xt, yt, 0])
L = [[9999999999]*(N+2) for i in range(N+2)]
for i in range(N+2):
    for j in range(i, N+2):
        x1, y1, r1 = XYR[i]
        x2, y2, r2 = XYR[j]
        L[i][j] = L[j][i] = max(((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2, 0.0)



num = N+2  
start = num-2

distance = [float('inf') for i in range(num)]  
prev = [float('inf') for i in range(num)]  
distance[start] = 0
q = []  
heapq.heappush(q, (0, start))  

while len(q) != 0:
    prov_cost, src = heapq.heappop(q)  

    
    if distance[src] < prov_cost:
        continue

    
    for destination, cost in enumerate(L[src]):
        if distance[destination] > distance[src] + cost:
            distance[destination] = distance[src] + cost  
            heapq.heappush(q, (distance[destination], destination))  
            prev[destination] = src  

print(distance[-1])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from pprint import pprint

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    d = {}
    q = []
    heapq.heappush(q, (0, s))

    while q:
        c, u = heapq.heappop(q)
        if u in d:
            continue
        d[u] = c
        for v in g[u]:
            if v not in d:
                heapq.heappush(q, (g[u][v] + c, v))
    return d


@mt
def slv(N, XY, YS, XT, YT, XYR):
    p = [(XY, YS, 0, -1), (XT, YT, 0, -2)]
    for i, (x, y, r) in enumerate(XYR):
        p.append((x, y, r, i))

    def cost(p1, p2):
        c = math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) - p1[2] - p2[2]
        return max(0, c)

    g = defaultdict(dict)
    for i in range(N+2):
        for j in range(N+2):
            if i == j:
                continue
            d = cost(p[i], p[j])
            g[p[i][3]][p[j][3]] = d
            g[p[j][3]][p[i][3]] = d

    return Dijkstra(g, -1)[-2]


def main():
    XS, YS, XT, YT = read_int_n()
    N = read_int()
    XYR = [read_int_n() for _ in range(N)]
    print(slv(N, XS, YS, XT, YT, XYR))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from pprint import pprint

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    d = {}
    q = []
    done = set()
    for v in g.keys():
        d[v] = sys.maxsize
    d[s] = 0
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, XY, YS, XT, YT, XYR):
    p = [(XY, YS, 0, -1), (XT, YT, 0, -2)]
    for i, (x, y, r) in enumerate(XYR):
        p.append((x, y, r, i))

    def cost(p1, p2):
        c = math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) - p1[2] - p2[2]
        return max(0, c)

    g = defaultdict(dict)
    for i in range(N+2):
        for j in range(N+2):
            if i == j:
                continue
            d = cost(p[i], p[j])
            g[p[i][3]][p[j][3]] = d
            g[p[j][3]][p[i][3]] = d

    return Dijkstra(g, -1)[-2]


def main():
    XS, YS, XT, YT = read_int_n()
    N = read_int()
    XYR = [read_int_n() for _ in range(N)]
    print(slv(N, XS, YS, XT, YT, XYR))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
import math

def culcD(a,b):
  x1,y1,r1=a
  x2,y2,r2=b
  return max(0,math.sqrt((x1-x2)**2+(y1-y2)**2)-(r1+r2))

A=[]

xs,ys,xg,yg=map(int,input().split())
A.append((xs,ys,0))
A.append((xg,yg,0))

V=defaultdict(int)
V[(0,1)]=(culcD(A[0],A[1]))
V[(1,0)]=(culcD(A[0],A[1]))

N=int(input())
for i in range(N):
  x,y,r=map(int,input().split())
  A.append((x,y,r))
  for j in range(len(A)-1):
    dist = culcD(A[j],A[-1])
    V[(i+2,j)]=dist
    V[(j,i+2)]=dist

def dijkstra(n):
  d=[float('inf')]*(n+2)
  d[0]=0
  used=[False]*(n+2)
  
  while True:
    v=-1
    for i in range(n+2):
      if used[i]==False and (v==-1 or d[i] < d[v]):
        v=i
    if v==-1:
      break
    used[v]=True
    for j in range(n+2):
      d[j]=min(d[j],d[v]+V[(j,v)])

  return d[1]

print(dijkstra(N))

Solution (Python):

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
def inpl(): return map(int, input().split())

sx, sy, tx, ty = inpl()
N = int(input())
X = np.zeros((1, N+2), dtype=np.float64)
Y = np.zeros((1, N+2), dtype=np.float64)
R = np.zeros((1, N+2), dtype=np.float64)

X[0][0] = sx
Y[0][0] = sy
X[0][N+1] = tx
Y[0][N+1] = ty

for i in range(N):
    X[0][i+1], Y[0][i+1], R[0][i+1] = inpl()

G = np.maximum(np.sqrt(np.square(X-X.T) + np.square(Y-Y.T)) - (R+R.T),
               np.zeros((N+2, N+2), dtype=np.float64)) 
G += np.diag(np.ones(N+2, dtype=np.float64)*np.inf)
G = csgraph_from_dense(G, null_value=np.inf)
print(dijkstra(G, indices=0)[-1])

Solution (Python):
def dist(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5


def dist_high(index1, index2):
    return max(dist(
            xyr[index1][0],
            xyr[index1][1],
            xyr[index2][0],
            xyr[index2][1]) - (xyr[index1][2] + xyr[index2][2]), 0)


def min_value_index(array):
    min_value = float("inf")
    min_index = -1
    for i, v in array:
        if min_value > v:
            min_value = v
            min_index = i
    return min_value, min_index

stx, sty, enx, eny = map(int, input().split())
n = int(input())
xyr = [[stx, sty, 0]] + [list(map(int, input().split())) for x in range(n)] + [[enx, eny, 0]]

nodes = {x: float("inf") for x in range(len(xyr))}
nodes[0] = 0
now = 0

while now != (len(xyr) - 1):
    for i in nodes.keys():
        if i == now:
            continue

        nodes[i] = min(nodes[i], nodes[now] + dist_high(now, i))
    del nodes[now]
    now = min_value_index(nodes.items())[1]
print(nodes[n + 1])

Solution (Python):
from heapq import *
from math import sqrt

def finddist(a,b):
    x1,y1,r1=a
    x2,y2,r2=b
    dx = x1 - x2
    dy = y1 - y2
    d = sqrt(dx*dx + dy*dy)
    return max(0, d - r1 -r2)


def dijkstra(c,s,t):
    found = set([(s,0)])
    dist ={s:0}
    notfound=set(c[1:])
    edgesinheap=[]
    newvert = s
    while notfound:
        if newvert == t:
            return dist[t]

        for x in notfound:
            heappush(edgesinheap, (dist[newvert]+finddist(newvert ,x), x, newvert))

        nextvertexfound = False
        while not nextvertexfound:
            d,nextvert, priv = heappop(edgesinheap)
            if nextvert not in found:
                nextvertexfound = True
                dist[nextvert] = d
                found.add(nextvert)
                notfound.remove(nextvert)
                newvert = nextvert

    return dist[t]





if __name__=="__main__":
    xs,ys,xt,yt=list(map(int,input().split()))
    N = int(input())
    circles = [(xs,ys,0), (xt,yt,0)]
    for _  in range(N):
        c=tuple(map(int, input().split()))
        circles.append(c)

    edges = []

    print(dijkstra(circles,circles[0],circles[1]))

Solution (Python):


import math
import itertools


INVALID = -1
INF = 10 ** 12


def dijkstra_dense(num_vs, adj_matrix, source, dest):
    dist = [INF for _ in range(num_vs)]
    visited = [False for _ in range(num_vs)]
    dist[source] = 0
    while True:
        u = min((j for j in range(num_vs) if not visited[j]),
                key=lambda i: dist[i], default=INVALID)
        if u == INVALID or dist[u] == INF:
            break
        visited[u] = True
        for v in range(num_vs):
            w = adj_matrix[u][v]
            if u != v and w < INF:
                new_len = dist[u] + w
                if new_len < dist[v]:
                    dist[v] = new_len
    return dist[dest]


def main():
    
    x0, y0, xf, yf = (int(x) for x in input().split())
    n = int(input())
    xs = [None for _ in range(n + 2)]
    ys = [None for _ in range(n + 2)]
    rs = [None for _ in range(n + 2)]
    xs[0], ys[0], rs[0] = x0, y0, 0
    xs[n + 1], ys[n + 1], rs[n + 1] = xf, yf, 0
    for i in range(1, n + 1):
        xs[i], ys[i], rs[i] = (int(z) for z in input().split())
    adj_matrix = [[INF for _ in range(n + 2)] for _ in range(n + 2)]
    for i, j in itertools.product(range(n + 2), repeat=2):
        adj_matrix[i][j] = max(0, math.hypot(xs[i] - xs[j],
                                             ys[i] - ys[j]) - (rs[i] + rs[j]))
    res = dijkstra_dense(n + 2, adj_matrix, 0, n + 1)
    print("{:.12f}".format(res))


if __name__ == '__main__':
    main()

Solution (Python):
xs,ys,xt,yt=list(map(int,input().split()))
N=int(input())
a=[]
for i in range(N):
	a.append(list(map(int,input().split())))





class Dijkstra(object):
	"""
	ダイクストラ法,(N^2)
	ステータス:distance(list),prev(list),size(int)
	distancemap[i][j]->Distance of edge i to j
	"""
	def __init__(self, distancemap, start):
		self.start=start
		self.size=len(distancemap)
		self.distance=[float("inf") for x in range(self.size)]
		self.distance[start]=0
		self.prev=[0 for x in range(self.size)]
		self.prev[start]=-1
		yet=list(range(self.size))
		yet.remove(start)
		now=start
		while(yet!=[]):
			nearest_num=0
			nearest_dis=float("inf")
			for i in yet:
				total_dis=distancemap[now][i]+self.distance[now]
				self.distance[i]=min(total_dis, self.distance[i])
				if self.distance[i]<=nearest_dis:
					nearest_dis=self.distance[i]
					nearest_num=i
			yet.remove(nearest_num)
			self.prev[nearest_num]=now
			now=nearest_num

	def route(self,goal):
		route=[]
		while(True):
			route.append(self.prev[goal])
			goal=self.prev[goal]
			if goal==self.start:
				break
		route.reverse()
		return(route)

import math
def solve(xs,ys,xt,yt,N,a):
	a.insert(0,[xs,ys,0])
	a.append([xt,yt,0])
	def distance(i,j):
		x1=a[i][0]
		y1=a[i][1]
		r1=a[i][2]
		x2=a[j][0]
		y2=a[j][1]
		r2=a[j][2]
		d=math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-r1-r2
		if d<0:
			d=0
		return(d)
	distancemap=[[0 for x in range(N+2)] for x in range(N+2)]
	for i in range(N+2):
		for j in range(N+2):
			if i>j:
				distancemap[i][j]=distancemap[j][i]
			else:
				distancemap[i][j]=distance(i,j)

	d=Dijkstra(distancemap, 0)
	return(d.distance.pop())

print(solve(xs, ys, xt, yt, N, a))

Solution (Python):
xs,ys,xt,yt=list(map(int,input().split()))
N=int(input())
a=[]
for i in range(N):
	a.append(list(map(int,input().split())))





class Dijkstra(object):
	"""
	ダイクストラ法,(N^2)
	ステータス:distance(list),prev(list),size(int)
	distancemap[i][j]->Distance of edge i to j
	"""
	def __init__(self, distancemap, start):
		self.start=start
		self.size=len(distancemap)
		self.distance=[float("inf") for x in range(self.size)]
		self.distance[start]=0
		self.prev=[0 for x in range(self.size)]
		self.prev[start]=-1
		yet=list(range(self.size))
		yet.remove(start)
		now=start
		while(yet!=[]):
			nearest_num=0
			nearest_dis=float("inf")
			for i in yet:
				total_dis=distancemap[now][i]+self.distance[now]
				self.distance[i]=min(total_dis, self.distance[i])
				if self.distance[i]<=nearest_dis:
					nearest_dis=self.distance[i]
					nearest_num=i
			yet.remove(nearest_num)
			self.prev[nearest_num]=now
			now=nearest_num

	def route(self,goal):
		route=[]
		while(True):
			route.append(self.prev[goal])
			goal=self.prev[goal]
			if goal==self.start:
				break
		route.reverse()
		return(route)

import math
def solve(xs,ys,xt,yt,N,a):
	a.insert(0,[xs,ys,0])
	a.append([xt,yt,0])
	def distance(i,j):
		x1=a[i][0]
		y1=a[i][1]
		r1=a[i][2]
		x2=a[j][0]
		y2=a[j][1]
		r2=a[j][2]
		d=math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-r1-r2
		if d<0:
			d=0
		return(d)
	distancemap=[[0 for x in range(N+2)] for x in range(N+2)]
	for i in range(N+2):
		for j in range(N+2):
			if i>j:
				distancemap[i][j]=distancemap[j][i]
			else:
				distancemap[i][j]=distance(i,j)

	d=Dijkstra(distancemap, 0)
	return(d.distance.pop())

print(solve(xs, ys, xt, yt, N, a))

Solution (Python):
xs,ys,xt,yt=list(map(int,input().split()))
N=int(input())
a=[]
for i in range(N):
	a.append(list(map(int,input().split())))





class Dijkstra(object):
	"""
	ダイクストラ法,(N^2)
	ステータス:distance(list),prev(list),size(int)
	distancemap[i][j]->Distance of edge i to j
	"""
	def __init__(self, distancemap, start):
		self.start=start
		self.size=len(distancemap)
		self.distance=[float("inf") for x in range(self.size)]
		self.distance[start]=0
		self.prev=[0 for x in range(self.size)]
		self.prev[start]=-1
		yet=list(range(self.size))
		yet.remove(start)
		now=start
		while(yet!=[]):
			nearest_num=0
			nearest_dis=float("inf")
			for i in yet:
				total_dis=distancemap[now][i]+self.distance[now]
				self.distance[i]=min(total_dis, self.distance[i])
				if self.distance[i]<=nearest_dis:
					nearest_dis=self.distance[i]
					nearest_num=i
			yet.remove(nearest_num)
			self.prev[nearest_num]=now
			now=nearest_num

	def route(self,goal):
		route=[]
		while(True):
			route.append(self.prev[goal])
			goal=self.prev[goal]
			if goal==self.start:
				break
		route.reverse()
		return(route)

import math
def solve(xs,ys,xt,yt,N,a):
	a.insert(0,[xs,ys,0])
	a.append([xt,yt,0])
	def distance(i,j):
		x1=a[i][0]
		y1=a[i][1]
		r1=a[i][2]
		x2=a[j][0]
		y2=a[j][1]
		r2=a[j][2]
		d=math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-r1-r2
		if d<0:
			d=0
		return(d)
	distancemap=[[0 for x in range(N+2)] for x in range(N+2)]
	for i in range(N+2):
		for j in range(N+2):
			if i>j:
				distancemap[i][j]=distancemap[j][i]
			else:
				distancemap[i][j]=distance(i,j)

	d=Dijkstra(distancemap, 0)
	return(d.distance.pop())

print(solve(xs, ys, xt, yt, N, a))

Solution (Python):
xs,ys,xt,yt=list(map(int,input().split()))
N=int(input())
a=[]
for i in range(N):
	a.append(list(map(int,input().split())))





class Dijkstra(object):
	"""
	ダイクストラ法,(N^2)
	ステータス:distance(list),prev(list),size(int)
	distancemap[i][j]->Distance of edge i to j
	"""
	def __init__(self, distancemap, start):
		self.start=start
		self.size=len(distancemap)
		self.distance=[float("inf") for x in range(self.size)]
		self.distance[start]=0
		self.prev=[0 for x in range(self.size)]
		self.prev[start]=-1
		yet=list(range(self.size))
		yet.remove(start)
		now=start
		while(yet!=[]):
			nearest_num=0
			nearest_dis=float("inf")
			for i in yet:
				total_dis=distancemap[now][i]+self.distance[now]
				self.distance[i]=min(total_dis, self.distance[i])
				if self.distance[i]<=nearest_dis:
					nearest_dis=self.distance[i]
					nearest_num=i
			yet.remove(nearest_num)
			self.prev[nearest_num]=now
			now=nearest_num

	def route(self,goal):
		route=[]
		while(True):
			route.append(self.prev[goal])
			goal=self.prev[goal]
			if goal==self.start:
				break
		route.reverse()
		return(route)

import math
def solve(xs,ys,xt,yt,N,a):
	a.insert(0,[xs,ys,0])
	a.append([xt,yt,0])
	def distance(i,j):
		x1=a[i][0]
		y1=a[i][1]
		r1=a[i][2]
		x2=a[j][0]
		y2=a[j][1]
		r2=a[j][2]
		d=math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-r1-r2
		if d<0:
			d=0
		return(d)
	distancemap=[[0 for x in range(N+2)] for x in range(N+2)]
	for i in range(N+2):
		for j in range(N+2):
			if i>j:
				distancemap[i][j]=distancemap[j][i]
			else:
				distancemap[i][j]=distance(i,j)

	d=Dijkstra(distancemap, 0)
	return(d.distance.pop())

print(solve(xs, ys, xt, yt, N, a))

Solution (Python):
from heapq import heappush, heappop

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

q = reads()
s = q[0] + q[1] * 1j
t = q[2] + q[3] * 1j

N = read()

p = []; r = []
for i in range(N):
  q = reads()
  p.append(q[0] + q[1] * 1j)
  r.append(q[2])


E = [[0]*(N+2) for _ in range(N+2)]
for i in range(N):
  for j in range(N):
    E[i][j] = max(abs(p[i] - p[j]) - r[i] - r[j], 0)

for i in range(N):
  E[N][i]   = E[i][N]   = max(abs(p[i] - s) - r[i], 0)
  E[N+1][i] = E[i][N+1] = max(abs(p[i] - t) - r[i], 0)

E[N][N+1] = E[N+1][N] = abs(t - s)

INF = 10**15 * 1.0

dist = [E[N][i] for i in range(N+2)] + [INF]
stab = [False] * (N+2)

stab[N] = True

for _ in range(N+1):
  i = N+2
  for j in range(N+2):
    if not stab[j] and dist[j] < dist[i]:
      i = j
  stab[i] = True
  for j in range(N+2):
    dist[j] = min(dist[j], dist[i] + E[i][j])

print(dist[N+1])

Solution (Python):
import math
import heapq
def dijkstra(s,m,n):
    visited=[0]*n
    d=[float("inf")]*n
    d[s]=0
    while True:
        mincost=float("inf")
        for i in xrange(n):
            if visited[i]!=2 and d[i]<mincost:
                mincost=d[i]
                u=i
        if mincost==float("inf"):
            break
        visited[u]=2
        for v in xrange(n):
            if visited[v]!=2:
                if d[u]+m[u][v]<d[v]:
                    d[v]=d[u]+m[u][v]
                    visited[v]=1
    return d

def main():
    xs,ys,xt,yt=map(int,raw_input().split())
    n=int(raw_input())
    c=[[xs,ys,0]]+[map(int,raw_input().split()) for _ in xrange(n)]+[[xt,yt,0]]
    dist=[[float("inf")]*(n+2) for _ in xrange(n+2)]
    for i in xrange(n+2):
        for j in xrange(n+2):
            if i==j:continue
            dist[i][j]=min(dist[i][j],dist[j][i],max(math.sqrt(abs(c[i][0]-c[j][0])**2+abs(c[i][1]-c[j][1])**2)-c[i][2]-c[j][2],0))
            dist[j][i]=dist[i][j]
    ans=dijkstra(0,dist,n+2)
    print(ans[n+1])
main()

Solution (Python):
import numpy as np
from collections import deque

xs, ys, xt, yt = map(int, raw_input().split())
N = int(raw_input())
X = [xs]
Y = [ys]
R = [0]
for _ in range(N):
    x, y, r = map(int, raw_input().split())
    X.append(x)
    Y.append(y)
    R.append(r)
X.append(xt)
Y.append(yt)
R.append(0)

X_np = np.array(X)
Y_np = np.array(Y)
R_np = np.array(R)

dist = np.zeros((N+2, N+2))
for i in range(N+2):
    dist[i, :] = np.maximum(np.sqrt((X_np - X_np[i])**2 + (Y_np - Y_np[i])**2) - (R_np + R_np[i]), 0)

cost = 4000000000.0 * np.ones(N+2)
cost[0] = 0

q = 0
unfixed_list = range(N+2)
unfixed_list.remove(q)


while len(unfixed_list) > 0:
    new_cost = cost[q] + dist[q, :]
    cost = np.minimum(cost, new_cost)
    q = unfixed_list[cost[unfixed_list].argmin()]
    unfixed_list.remove(q)
    

print cost[N+1]

Solution (Python):
from heapq import heappush, heappop
from math import sqrt
xs, ys, xt, yt = map(int, raw_input().split())
n = input()
ps = [map(int, raw_input().split()) for i in xrange(n)]
cant = [0]*n
for i in xrange(n):
    x0, y0, r0 = ps[i]
    for j in xrange(n):
        x1, y1, r1 = ps[j]
        if i == j or r0 > r1: continue
        if (x0 - x1)**2 + (y0 - y1)**2 <= (r1 - r0)**2:
            cant[i] = 1
            break

EPS = 1e-10
que = []
dist = [10**18+7]*n
def calc(x0, y0, r0, x1, y1, r1):
    v = (x0 - x1)**2 + (y0 - y1)**2
    if v <= (r0+r1)**2:
        return 0.
    return sqrt(v) - r0 - r1
for i in xrange(n):
    if cant[i]: continue
    x, y, r = ps[i]
    d = dist[i] = calc(xs, ys, 0, x, y, r)
    heappush(que, (d, i))
while que:
    d, v = heappop(que)
    if dist[v] < d:
        continue
    x0, y0, r0 = ps[v]
    for t in xrange(n):
        if v == t or cant[t]: continue
        x1, y1, r1 = ps[t]
        nd = calc(x0, y0, r0, x1, y1, r1)
        if d+nd < dist[t]:
            dist[t] = d+nd
            heappush(que, (d+nd, t))
ans = sqrt((xs - xt)**2 + (ys - yt)**2)
for i in xrange(n):
    if cant[i]: continue
    x, y, r = ps[i]
    d = calc(xt, yt, 0, x, y, r) + dist[i]
    ans = min(ans, d)
print "%.010f" % ans

Solution (Python):
xs,ys,xt,yt = map(int, input().split())
n = int(input())
c = [(xs,ys, 0),(xt,yt,0)]
for i in range(n):
    x,y,r = map(int, input().split())
    c.append((x,y,r))

def circle_circle(ax,ay,ar,bx,by,br):
    d =((ax-bx)**2 + (ay-by)**2)**0.5
    return max(0, d-(ar+br))

def dijkstra(V, edges, root):
    import heapq

    visited = [False] * V
    nodes = [[] for i in range(V)]
    cost = [[] for i in range(V)]

    for e in edges:
        s, t, d = e
        nodes[s].append(t)
        cost[s].append(d)

    dist = [float('inf')] * V
    dist[root] = 0

    h = [(0, root)]
    while h:
        c, v = heapq.heappop(h)
        if visited[v]:
            continue
        visited[v] = True
        for i in range(n+1):
            t = nodes[v][i]
            nc = c + cost[v][i]
            if dist[t] > nc:
                dist[t] = nc
                heapq.heappush(h, (nc, t))
    return dist
edges = []
for i in range(n+1):
    for j in range(i+1, n+2):
        d = circle_circle(c[i][0],c[i][1],c[i][2],c[j][0],c[j][1],c[j][2])
        edges.append((i,j,d))
        edges.append((j,i,d))
dij = dijkstra(n+2, edges, 0)
print(dij[1])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def main():
    sx,sy,ex,ey = list(map(int, input().split()))
    n = int(input())
    f = [False] * n
    a = [list(map(int, input().split())) for _ in range(n)]
    aa = [[inf]*n for _ in range(n)]
    k = [0] * n
    for i in range(n):
        ai = a[i]
        t = math.sqrt((sx-ai[0])**2 + (sy-ai[1])**2) - ai[2]
        if t <= 0:
            t = 0
        k[i] = t

    for i in range(n-1):
        ai = a[i]
        for j in range(i+1, n):
            aj = a[j]
            t = math.sqrt((aj[0]-ai[0])**2 + (aj[1]-ai[1])**2) - ai[2] - aj[2]
            if t < 0:
                t = 0
            aa[i][j] = t
            aa[j][i] = t

    while True:
        mi = -1
        mk = inf
        for i in range(n):
            if f[i]:
                continue
            if k[i] < mk:
                mk = k[i]
                mi = i
        if mi < 0:
            break

        aai = aa[mi]
        f[mi] = True
        
        
        for j in range(n):
            if aai[j] + k[mi] < k[j]:
                k[j] = aai[j] + k[mi]

    r = math.sqrt((sx-ex)**2 + (sy-ey)**2)
    for i in range(n):
        ai = a[i]
        t = math.sqrt((ex-ai[0])**2 + (ey-ai[1])**2) - ai[2]
        if t < 0:
            t = 0
        
        if r > k[i] + t:
            r = k[i] + t

    
    
    return r


print(main())