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,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else 1<<33) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    remain=set(range(n))
    
    while q:
        dist,cur=heappop(q)
        if cur not in remain:
            continue
        remain.remove(cur)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


sx,sy,gx,gy=LI()
n=I()
 
c=[(sx,sy,0),(gx,gy,0)]
for i in range(n):
    c+=[LI()]

n+=2
g=[[]for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        x,y,r1=c[i]
        s,t,r2=c[j]
        d=math.hypot(x-s,y-t) -r1 -r2
        if d<0:d=0
        g[i].append((j,d))
        g[j].append((i,d))
d,_=dijkstra(g,0)
print(d[1])

Solution (Python):
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else 1<<33) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    remain=set(range(n))
    
    while q:
        dist,cur=heappop(q)
        if cur not in remain:
            continue
        remain.remove(cur)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


sx,sy,gx,gy=LI()
n=I()
 
c=[(sx,sy,0),(gx,gy,0)]
for i in range(n):
    c+=[LI()]

n+=2
g=[[]for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        x,y,r1=c[i]
        s,t,r2=c[j]
        d=((x-s)**2+(y-t)**2)**0.5 -r1 -r2
        if d<0:d=0
        g[i].append((j,d))
        g[j].append((i,d))
d,_=dijkstra(g,0)
print(d[1])

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

def main():
	sx, sy, gx, gy = map(int, input().split())
	n = int(input())
	v = [(sx, sy, 0), (gx, gy, 0)]
	for _ in range(n):
		v.append(tuple(map(int, input().split())))
	d = np.full((n + 2, n + 2), np.inf)
	for i, p1 in enumerate(v):
		for j, p2 in enumerate(v[i + 1:]):
			d[i][i + j + 1] = max(0, hypot(p1[0] - p2[0], p1[1] - p2[1]) - p1[2] - p2[2])
	print(dijkstra(csgraph_from_dense(d,null_value=np.inf),False,0)[1])

if __name__ == '__main__':
	main()

Solution (Python):
from heapq import*

def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

import sys
input = sys.stdin.buffer.readline
from math import hypot
sx,sy,gx,gy=map(int,input().split())
n=int(input())
v=[(sx,sy,0),(gx,gy,0)]
for _ in range(n):
	v.append(tuple(map(int,input().split())))
con=[[] for _ in range(n+2)]
for i,p1 in enumerate(v):
	for j,p2 in enumerate(v[i+1:]):
		t=max(0,hypot(p1[0]-p2[0],p1[1]-p2[1])-p1[2]-p2[2])
		con[i].append((i+j+1,t))
		con[i+j+1].append((i,t))
print(Dijkstra(con)[1])

Solution (Python):
import math
import heapq

x1, y1, x2, y2 = map(int, input().split())
N = int(input())
circles = [(x1, y1, 0), (x2, y2, 0)]
for i in range(N):
    x, y, r = map(int, input().split())
    circles.append((x, y, r))
N += 2

INF = 10 ** 12
dists = [[INF] * N for _ in range(N)]
for i in range(N):
    xi, yi, ri = circles[i]
    for j in range(N):
        xj, yj, rj = circles[j]
        d = math.sqrt(abs(xi - xj) ** 2.0 + abs(yi - yj) ** 2.0) - ri - rj
        dists[i][j] = dists[j][i] = max(d, 0)

mincost = [None] * N
hp = [(0.0, 0)]
while hp:
    mc, node = heapq.heappop(hp)
    if mincost[node] is not None:
        continue
    mincost[node] = mc
    for i in range(N):
        if mincost[i] is None:
            heapq.heappush(hp, (mc + dists[node][i], i))
print(mincost[1])

Solution (Python):
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N 
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N 
        self.prev = prev = [-1] * N 
        dist[s] = 0
        n_visited = 0 
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue 
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Solution (Python):
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N 
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N 
        self.prev = prev = [-1] * N 
        dist[s] = 0
        n_visited = 1 
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def cost(i,j):
        x1,y1,r1=xyr[i]
        x2, y2, r2 = xyr[j]
        res=((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2
        return max(res,0)

    sx,sy,gx,gy=MI()
    n=II()
    xyr=LLI(n)
    xyr=[[sx,sy,0]]+xyr+[[gx,gy,0]]
    n+=2
    to=[[] for _ in range(n)]
    for i in range(n):
        x1,y1,r1=xyr[i]
        for j in range(i):
            x2, y2, r2 = xyr[j]
            c=cost(i,j)
            to[i].append((j,c))
            to[j].append((i,c))
    hp=[]
    fin=[False]*n
    heappush(hp,(0,0))
    while hp:
        d,u=heappop(hp)
        if fin[u]:continue
        fin[u]=True
        if u==n-1:
            print(d)
            exit()
        for v,c in to[u]:
            if fin[v]:continue
            heappush(hp,(d+c,v))

main()

Solution (Python):
import sys
import heapq
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def dist(x1, y1, x2, y2):
    dx = x1 - x2
    dy = y1 - y2
    return (dx ** 2 + dy ** 2) ** 0.5


xs, ys, xg, yg = map(int, input().split())
N = int(input())
XYR = [tuple(map(int, input().split())) for _ in range(N)]
edge = [[] for _ in range(N+2)]



for i in range(N - 1):
    xi, yi, ri = XYR[i]
    for j in range(i + 1, N):
        xj, yj, rj = XYR[j]
        d = max(0, dist(xi, yi, xj, yj) - ri - rj)
        edge[i].append((j, d))
        edge[j].append((i, d))

for i in range(N):
    xi, yi, ri = XYR[i]

    ds = max(0, dist(xi, yi, xs, ys) - ri)
    edge[i].append((N, ds))
    edge[N].append((i, ds))

    dg = max(0, dist(xi, yi, xg, yg) - ri)
    edge[i].append((N + 1, dg))
    edge[N + 1].append((i, dg))

d = dist(xs, ys, xg, yg)
edge[N].append((N + 1, d))
edge[N + 1].append((N, d))


inf = 10**18
dist = [inf] * (N + 10)
dist[N] = 0
que = [(0, N)]
while que:
    c, s = heapq.heappop(que)
    if dist[s] < c:
        continue
    for t, cost in edge[s]:
        if dist[t] > dist[s] + cost:
            dist[t] = dist[s] + cost
            heapq.heappush(que, (dist[t], t))

print(dist[N + 1])

Solution (Python):
xs, ys, xt, yt = map(int, input().split())
n = int(input())
X = [[0, 0, 0] for _ in range(n+2)]
X[0] = [xs, ys, 0]
X[n+1] = [xt, yt, 0]
R = [0]*n
for i in range(n):
    x, y, r = map(int, input().split())
    X[i+1] = [x, y, r]

import math
edge = [[] for _ in range(n+2)]
for i in range(n+1):
    x1, y1, r1 = X[i]
    for j in range(i+1, n+2):
        x2, y2, r2 = X[j]
        l = math.sqrt((x1-x2)**2+(y1-y2)**2)
        edge[i].append((max(l-r1-r2, 0), j))
        edge[j].append((max(l-r1-r2, 0), i))

import heapq
def dijkstra_heap(s):
    d = [float("inf")] * (n+2)
    used = [True] * (n+2) 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

d = dijkstra_heap(0)
print(d[-1])

Solution (Python):
import math
x1, y1, x2, y2 = [int(i) for i in input().split()]
n = int(input())

xy = [[x1, y1, 0]]
for _ in range(n):
    xy.append([int(i) for i in input().split()])
xy.append([x2, y2, 0])


def dif(x, y):
    return max(0, math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) - x[2] - y[2])




q = set([i for i in range(n + 2)])
mi = [10 ** 16] * (n + 2)
mi[0] = 0

while q:
    u = -1
    mm = 10**16
    for i in q:
        if mm > mi[i]:
            mm = mi[i]
            u = i
    
    q.remove(u)
    for i in q:
        mi[i] = min(mi[i], mi[u] + dif(xy[i], xy[u]))

print(mi[-1])

Solution (Python):
class Dijkstra():
  class Edge():
    
    def __init__(self,_to,_cost):
      self.to=_to
      self.cost=_cost
  def __init__(self,V):
    
    self.G=[[] for i in range(V)]
    self._E=0
    self._V=V
  def E(self):
    
    return self._E
  def V(self):
    
    return self._V
  def add(self, _from, _to, _cost):
    
    self.G[_from].append(self.Edge(_to, _cost))
    self._E+=1
  def shortest_path(self,s):
    
    import heapq
    que=[]
    d=[float('inf')]*self._V
    d[s]=0
    heapq.heappush(que,(0,s))
    while que:
      cost,v=heapq.heappop(que)
      if d[v]<cost:continue
      for i in range(len(self.G[v])):
        e=self.G[v][i]
        if d[e.to]>d[v]+e.cost:
          d[e.to]=d[v]+e.cost
          heapq.heappush(que,(d[e.to],e.to))
    return d

import sys
input=sys.stdin.readline
xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[list(map(int,input().split())) for i in range(n)]
graph=[[10**9]*(n+2) for i in range(n+2)]
graph[0][n+1]=graph[n+1][0]=((xs-xt)**2+(ys-yt)**2)**0.5
for i in range(1,n+1):
  for j in range(1,n+1):
    d=((xyr[i-1][0]-xyr[j-1][0])**2+(xyr[i-1][1]-xyr[j-1][1])**2)**0.5
    graph[i][j]=graph[j][i]=max(0,d-xyr[i-1][2]-xyr[j-1][2])
for i in range(1,n+1):
  d1=((xs-xyr[i-1][0])**2+(ys-xyr[i-1][1])**2)**0.5
  d2=((xt-xyr[i-1][0])**2+(yt-xyr[i-1][1])**2)**0.5
  graph[0][i]=graph[i][0]=max(0,d1-xyr[i-1][2])
  graph[n+1][i]=graph[i][n+1]=max(0,d2-xyr[i-1][2])
d=Dijkstra(n+2)
for i in range(n+2):
  for j in range(n+2):
    d.add(i,j,graph[i][j])
print(d.shortest_path(0)[n+1])

Solution (Python):
import sys
import time
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


def dijkstra(graph, start, n):
    h = []
    heapq.heappush(h, (0, start))
    costs = [INF for _ in range(n)]
    while h:
        cost, cur = heapq.heappop(h)
        if costs[cur] != INF:
            continue
        costs[cur] = cost
        for edge in graph[cur]:
            ecost, tgt = edge
            if costs[tgt] == INF:
                heapq.heappush(h, (cost + ecost, tgt))

    return costs


def dist(x1, y1, x2, y2):
    return math.sqrt(abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2)


def main():
    xs, ys, xe, ye = getlist()
    N = getN()
    graph = [[] for i in range(N + 3)]
    circles = []
    circles.append([xs, ys, 0])
    circles.append([xe, ye, 0])
    for i in range(N):
        circles.append(getlist())

    for i in range(N+1):
        for j in range(i+1, N+2):
            
            x1, y1, r1 = circles[i]
            x2, y2, r2 = circles[j]
            ray = max(dist(x1, y1, x2, y2) - r1 - r2, 0)
            graph[i].append((ray, j))
            graph[j].append((ray, i))

    print(dijkstra(graph, 0, N+2)[1])

if __name__ == '__main__':
    main()

Solution (Python):

sx,sy,tx,ty = map(int,input().split())
raw = [[sx,sy,0]]
n = int(input()) + 2
for _ in range(n-2):
  raw.append(list(map(int,input().split())))
raw.append([tx,ty,0])
dist = []
for i in range(n):
  add = []
  for j in range(n):
    tmp = (raw[i][0]-raw[j][0])**2 + (raw[i][1]-raw[j][1])**2
    tmp **= .5
    tmp -= raw[i][2] + raw[j][2]
    if tmp < 0:
      tmp = 0
    add.append(tmp)
  dist.append(add)

inf = 10**12
now = []
for i in range(n):
  now.append([dist[0][i],i])
now[0][0] = inf
for _ in range(n-1):
  d,j = min(now)
  if j == n-1:
    print(d)
  now[j][0] = inf
  for i in range(n):
    if now[i][0] == inf:
      continue
    if now[i][0] > d + dist[i][j]:
      now[i][0] = d + dist[i][j]

Solution (Python):






from heapq import heappush, heappop
INF = 10**10
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in enumerate(G[v]):
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

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

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

def d(pj,pk):
    dis = (pj[0]-pk[0])**2+(pj[1]-pk[1])**2
    return(max(dis**(1/2)-pk[2]-pj[2],0))

D = [[d(p[i],p[j]) for i in range(n+2)] for j in range(n+2)]

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

Solution (Python):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy


idle=10**13
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])
XYR.append([xs,ys,0])
"""for i in range(len(XYR)):
    XYR[i][0]*=idle
    XYR[i][1]*=idle
    XYR[i][2]*=idle"""
kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=t
        kyori[m][i]=t
stack=sorted(kyori[-1])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=kyori[-1][i]
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)
visited=set([len(XYR)-1])
while stack:
    m=heappop(stack)
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+m
            if Pdic[i]>nm:
                Pdic[i]=nm
                heappush(stack,nm)
                if not nm in kyoriset:
                    kyoriset.add(nm)
                    dic.update({nm:[i]})
                else:
                    dic[nm].append(i)

Solution (Python):


import sys
from math import hypot

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    
    res = [INF] * N
    
    que = [(0, src)]
    res[src] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        if res[cur] < dist:
            continue
        
        for nxt, cost in nodes[cur]:
            
            if dist + cost < res[nxt]:
                res[nxt] = dist + cost
                
                heappush(que, (dist+cost, nxt))
    
    return res

sx, sy, tx, ty = MAP()
N = INT()
XYR = []
for i in range(N):
    x, y, r = MAP()
    XYR.append((x, y, r))

XYR.append((sx, sy, 0))
XYR.append((tx, ty, 0))
N += 2


nodes = [[] for i in range(N)]
for i in range(N):
    x1, y1, r1 = XYR[i]
    for j in range(i+1, N):
        x2, y2, r2 = XYR[j]
        dist = hypot(x1-x2, y1-y2)
        
        cost = max(dist - (r1+r2), 0)
        nodes[i].append((j, cost))
        nodes[j].append((i, cost))

res = dijkstra(N, nodes, N-2)
print(res[N-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 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):
import heapq

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

def dist(x, y, s, t):
    return ((x-s)**2 + (y-t)**2)**0.5
    
h = []
for i in range(N):
    heapq.heappush(h, (max(0, dist(xs, ys, L[i][0], L[i][1])-L[i][2]), i))

inf = 10**10
d = [inf]*N
cnt = 0
while cnt < N:
    temp = heapq.heappop(h)
    if d[temp[1]] < inf:
        continue
    cnt += 1
    d[temp[1]] = temp[0]
    for i in range(N):
        if d[i] < inf:
            continue
        heapq.heappush(h, (temp[0]+max(0, dist(L[i][0], L[i][1], L[temp[1]][0], L[temp[1]][1])-L[i][2]-L[temp[1]][2]), i))

ans = dist(xs, ys, xt, yt)
for i in range(N):
    ans = min(ans, d[i]+max(0, dist(xt, yt, L[i][0], L[i][1])-L[i][2]))

print(ans)