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 heapq import heappop,heappush
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


xs,ys,xt,yt = MI()
N = I()
XYR = []
for _ in range(N):
    XYR.append(tuple(MI()))
XYR.append((xs,ys,0))  
XYR.append((xt,yt,0))  

Graph = [[0]*(N+2) for _ in range(N+2)]  
for i in range(N+1):
    x0,y0,r0 = XYR[i]
    for j in range(i+1,N+2):
        x1,y1,r1 = XYR[j]
        Graph[i][j] = max(0,((x1-x0)**2+(y1-y0)**2)**.5-r0-r1)
        Graph[j][i] = max(0,((x1-x0)**2+(y1-y0)**2)**.5-r0-r1)



dist = [10**10]*(N+2)  
dist[N] = 0
q = []
heappush(q,(0,N))
flag = [0]*(N+2)
while q:
    d,i = heappop(q)
    if flag[i] == 1:
        continue
    flag[i] = 1

    for j in range(N+2):
        if flag[j] == 0:
            new_d = d+Graph[i][j]
            if new_d < dist[j]:
                dist[j] = new_d
                heappush(q,(new_d,j))

print(dist[N+1])

Solution (Python):
xs,ys,xe,ye=map(int,input().split())
n=int(input())
xyr=[tuple(map(int,input().split())) for _ in range(n)]
xyr.append((xs,ys,0))
xyr.append((xe,ye,0))
d=[[0]*(n+2) for _ in range(n+2)]
for i in range(n+1):
  for j in range(i+1,n+2):
    x,y,r=xyr[i]
    nx,ny,nr=xyr[j]
    tmp=((x-nx)**2+(y-ny)**2)**0.5
    tmp-=r+nr
    tmp=max(tmp,0)
    d[i][j]=tmp
    d[j][i]=tmp



inf=float('inf')
seen=[inf]*(n+2)
seen[-2]=0
mi=set(range(n+2))

while mi:
  min_idx=0
  min_d=inf
  for v in mi:
    if min_d>seen[v]:
      min_d=seen[v]
      min_idx=v
  v=min_idx
  mi.discard(v)
  if v==n+1:break
  for nv in mi:
    seen[nv]=min(seen[nv],seen[v]+d[v][nv])
print(seen[-1])

Solution (Python):
from math import sqrt
from sys import stdin
input = stdin.buffer.readline

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

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

    
    inf = float('inf')
    dic = {i: inf for i in range(n+2)}
    dic[0] = 0.0
    while True:
        ind, cost = min(dic.items(), key=lambda x: x[1])
        dic.pop(ind)

        if ind == 1:
            print(cost)
            break

        x, y, r = xyr[ind]
        for i, old_cost in dic.items():
            xi, yi, ri = xyr[i]
            new_cost = max(sqrt((x-xi)*(x-xi)+(y-yi)*(y-yi))-(r+ri), 0.0) + cost
            if new_cost < old_cost:
                dic[i] = new_cost

main()

Solution (Python):
from math import sqrt
from sys import stdin
input = stdin.buffer.readline

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

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

    
    inf = float('inf')
    dic = {i: inf for i in range(n+2)}
    dic[0] = 0.0
    while True:
        ind, cost = min(dic.items(), key=lambda x: x[1])
        dic.pop(ind)

        if ind == 1:
            print(cost)
            break

        x, y, r = xyr[ind]
        for i, old_cost in dic.items():
            xi, yi, ri = xyr[i]
            new_cost = max(sqrt((x-xi)*(x-xi)+(y-yi)*(y-yi))-(r+ri), 0.0) + cost
            if new_cost < old_cost:
                dic[i] = new_cost

main()

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

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

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

    
    heap = []
    heappush(heap, (0.0, 0))
    times = [10**19] * (n+2)
    times[0] = 0
    yet = set(range(n+2))
    while True:
        time, ind = heappop(heap)

        if ind == 1:
            print(time)
            break

        if times[ind] == time:
            yet.remove(ind)
            x, y, r = xyr[ind]
            for i in yet:
                xi, yi, ri = xyr[i]
                new_time = max(sqrt((x-xi)*(x-xi)+(y-yi)*(y-yi))-(r+ri), 0.0) + time
                if new_time < times[i]:
                    times[i] = new_time
                    heappush(heap, (new_time, i))

main()

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

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

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

    
    heap = []
    heappush(heap, (0.0, 0))
    seen = [-1] * (n+2)
    yet = set(range(n+2))
    while True:
        time, ind = heappop(heap)

        if ind == 1:
            print(time)
            break

        if seen[ind] == -1:
            seen[ind] = time
            yet.remove(ind)
            x, y, r = xyr[ind]
            for i in yet:
                xi, yi, ri = xyr[i]
                heappush(heap, (max(sqrt((x-xi)*(x-xi)+(y-yi)*(y-yi))-r-ri, 0.0)+time, i))

main()

Solution (Python):
xs, ys, xt, yt = map(int,input().split())
N = int(input())
L = [[xs, ys, 0], [xt, yt, 0]]

for _ in range(N):
    L.append(list(map(int,input().split())))

V = N + 2
G = [[] for _ in range(N+2)]
s = 0

for i in range(N+2):
    for j in range(N+2):
        if i != j:
            G[i].append([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]))])


INF = float('inf')

import heapq

def dijkstra(s):
    d = [INF for _ in range(V)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))

    return d

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

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

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    
    def dijkstra(s):
        hq = [(0, s)]
        cost = [float('inf')] * (n + 2)
        cost[s] = 0
        while hq:
            c, v = heapq.heappop(hq)
            if c > cost[v]:
                continue
            for d, u in edges[v]:
                tmp = d + cost[v]
                if tmp < cost[u]:
                    cost[u] = tmp
                    heapq.heappush(hq, (tmp, u))
        return cost[-1]
    
    circles = []
    circles.append([xs, ys, 0])
    for _ in range(n):
        circles.append(list(map(int, input().split())))
    circles.append([xt, yt, 0])
    edges = [[] for _ in range(n + 2)]
    for i in range(n + 2):
        for j in range(i + 1, n + 2):
            dx = circles[i][0] - circles[j][0]
            dy = circles[i][1] - circles[j][1]
            d = (dx ** 2 + dy ** 2) ** 0.5
            r = circles[i][2] + circles[j][2]
            edges[i].append([max(0, d - r), j])
            edges[j].append([max(0, d - r), i])

    ans = dijkstra(0)
    print(ans)
    
main()

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

def dijkstra(n, s, edges):
    hq = [(0, s)]
    cost = [float('inf')] * n
    cost[s] = 0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]:
            continue
        for d, u in edges[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost[-1]

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    circles = []
    circles.append([xs, ys, 0])
    for _ in range(n):
        circles.append(list(map(int, input().split())))
    circles.append([xt, yt, 0])
    edges = [[] for _ in range(n + 2)]
    for i in range(n + 2):
        for j in range(i + 1, n + 2):
            dx = circles[i][0] - circles[j][0]
            dy = circles[i][1] - circles[j][1]
            d = (dx ** 2 + dy ** 2) ** 0.5
            r = circles[i][2] + circles[j][2]
            edges[i].append([max(0, d - r), j])
            edges[j].append([max(0, d - r), i])

    ans = dijkstra(n + 2, 0, edges)
    print(ans)
    
main()

Solution (Python):
from heapq import heappop, heappush

sx, sy, tx, ty = map(int, input().split())
n = int(input())
barriers = [tuple(map(int, input().split())) for _ in range(n)]
barriers.append((tx, ty, 0))
barriers.append((sx, sy, 0))
s = n + 1
t = n
q = [(0., s)]
visited = [False] * (n + 2)
while q:
    cost, v = heappop(q)
    if v == t:
        print(cost)
        break
    if visited[v]:
        continue
    visited[v] = True
    vx, vy, vr = barriers[v]
    for u in range(n + 1):
        if visited[u]:
            continue
        ux, uy, ur = barriers[u]
        new_cost = max(0, ((vx - ux) ** 2 + (vy - uy) ** 2) ** 0.5 - vr - ur)
        heappush(q, (cost + new_cost, u))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


xs,ys,xt,yt = list(map(int, input().split()))
n = int(input())
xyr = [None]*(n+2)
for i in range(n):
    xyr[i] = tuple(map(int, input().split()))
from itertools import product
ns = [[] for _ in range(n+2)]
s = n
t = n+1
xyr[s] = (xs,ys,0)
xyr[t] = (xt,yt,0)
for i,j in product(range(n+2), range(n+2)):
    if i<j:
        d = max(0, ((xyr[i][0]-xyr[j][0])**2 + (xyr[i][1]-xyr[j][1])**2)**0.5 - (xyr[i][2]+xyr[j][2]))
        ns[i].append((d,j))
        ns[j].append((d,i))
def dijkstra(start):
    import heapq
    vals = [None] * (n+2)
    h = [(0, start)] 
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        if u==t:
            break
        if val>vals[u]:
          continue
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
vals = dijkstra(s)
ans = vals[t]
print(ans)

Solution (Python):
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Solution (Python):
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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





x1, y1, x2, y2 = getNM()
place = [(x1, y1, 0)]
N = getN()
for i in range(N):
    x, y, r = getNM()
    place.append((x, y, r))
place.append((x2, y2, 0))
N += 2




def calc(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def dijkstra(n, start):
    dist = [float('inf')] * n
    pos = [(0, start)]
    heapify(pos)
    dist[start] = 0

    while len(pos):
        cost, u = heappop(pos)

        if dist[u] < cost:
            continue
        
        for i in range(N):
            if i == u:
                continue
            dis = calc(place[u][0], place[u][1], place[i][0], place[i][1])
            opt = max(dis - place[u][2] - place[i][2], 0)
            if dist[u] + opt < dist[i]:
                dist[i] = dist[u] + opt
                heappush(pos, (dist[u] + opt, i))

    return dist

print(dijkstra(N, 0)[-1])

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

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








xyr = [[xs,ys,0]] + xyr + [[xt,yt,0]]

cost = {}
for s in range(0,N+1):
    for t in range(s+1,N+2):
        x1,y1,r1 = xyr[s]
        x2,y2,r2 = xyr[t]
        R = pow((x2-x1)**2+(y2-y1)**2,0.5)
        c = max(0, R-r1-r2)
        cost[(s,t)] = c
        cost[(t,s)] = c

h = [(0,0)]
dist = [10**15] * (N+2)
dist[0] = 0
while h:
    d,v = heappop(h)
    if dist[v] < d:
        continue
    for nv in range(N+2):
        if v == nv:
            continue
        temp = d + cost[(v,nv)]
        if temp < dist[nv]:
            dist[nv] = temp
            heappush(h, (temp,nv))

print(dist[N+1])

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


def dijkstra(s, n, edges):
    INF = float('inf')
    d = [INF] * n
    d[s] = 0
    import heapq
    pq = [(0, s)]
    while len(pq):
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        
        for nv, v2nvcost in enumerate(edges[v]):
            if c + v2nvcost < d[nv]:
                d[nv] = c + v2nvcost
                heapq.heappush(pq, (d[nv], nv))
    return d


dist = dijkstra(0, n + 2, edge)
print(dist[1])

Solution (Python):

import sys


def solve(x_s: int, y_s: int, x_t: int, y_t: int, N: int, x: "List[int]", y: "List[int]", r: "List[int]"):
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    x.extend([x_s, x_t])
    y.extend([y_s, y_t])
    r.extend([0, 0])
    p = np.column_stack((x, y))
    diff = np.expand_dims(p, axis=1) - np.expand_dims(p, axis=0)
    dist = np.sqrt(np.sum(diff ** 2, axis=-1))
    delta = 0.5
    mat = csr_matrix(((dist - r).T - r).clip(min=0)-delta)
    mat.data += delta
    return dijkstra(mat, indices=N)[N+1]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    x_s = int(next(tokens))  
    y_s = int(next(tokens))  
    x_t = int(next(tokens))  
    y_t = int(next(tokens))  
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    r = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        r[i] = int(next(tokens))
    print(solve(x_s, y_s, x_t, y_t, N, x, y, r))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):

import sys


def solve(x_s: int, y_s: int, x_t: int, y_t: int, N: int, x: "List[int]", y: "List[int]", r: "List[int]"):
    import numpy as np
    from scipy.sparse import csr_matrix, coo_matrix
    from scipy.sparse.csgraph import dijkstra
    x.extend([x_s, x_t])
    y.extend([y_s, y_t])
    r.extend([0, 0])
    p = np.column_stack((x, y))
    diff = np.expand_dims(p, axis=1) - np.expand_dims(p, axis=0)
    dist = np.sqrt(np.sum(diff ** 2, axis=-1))
    mat = ((dist - r).T - r).clip(min=1e-20)    
    return '{:.10f}'.format(dijkstra(csr_matrix(mat), indices=N)[N+1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    x_s = int(next(tokens))  
    y_s = int(next(tokens))  
    x_t = int(next(tokens))  
    y_t = int(next(tokens))  
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    r = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        r[i] = int(next(tokens))
    print(solve(x_s, y_s, x_t, y_t, N, x, y, r))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

xy=list(map(int,input().split()))
n=int(input())
xyr=[list(map(int,input().split())) for i in range(n)]

def dijkstra(s,e):
    hq = [(0, s)]
    heapq.heapify(hq) 
    cost = [float('inf')] * n 
    cost[s] = 0 
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: 
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost


n,w = n,(n+2)*(n+1)//2 

edge = [[] for i in range(n+2)]

for i in range(n):
    for j in range(i+1,n):
        x1,y1,r1=xyr[i]
        x2,y2,r2=xyr[j]
        dis=math.sqrt((x2-x1)**2+(y2-y1)**2)
        edge[i+1].append((max(0,dis-r1-r2),j+1))
        edge[j+1].append((max(0,dis-r1-r2),i+1))
for i in range(n):
    x1,y1,r1=xyr[i]
    dis=math.sqrt((xy[0]-x1)**2+(xy[1]-y1)**2)
    edge[0].append((max(0,dis-r1),i+1))
    edge[i+1].append((max(0,dis-r1),0))
    dis=math.sqrt((xy[2]-x1)**2+(xy[3]-y1)**2)
    edge[n+1].append((max(0,dis-r1),i+1))
    edge[i+1].append((max(0,dis-r1),n+1))
edge[0].append((math.sqrt((xy[0]-xy[2])**2+(xy[1]-xy[3])**2),n+1))
edge[n+1].append((math.sqrt((xy[0]-xy[2])**2+(xy[1]-xy[3])**2),0))

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


xs,ys,xt,yt = list(map(int, input().split()))
n = int(input())
xyr = [None]*(n+2)
for i in range(n):
    xyr[i] = tuple(map(int, input().split()))
from itertools import product

data = []
rs = []
cs = []
s = n
t = n+1
xyr[s] = (xs,ys,0)
xyr[t] = (xt,yt,0)
for i,j in product(range(n+2), range(n+2)):
    if i<j:
        d = max(0, ((xyr[i][0]-xyr[j][0])**2 + (xyr[i][1]-xyr[j][1])**2)**0.5 - (xyr[i][2]+xyr[j][2]))
        data.append(d)
        rs.append(i)
        cs.append(j)
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n+2, n+2))
ans = scipy.sparse.csgraph.dijkstra(m, indices=t, directed=False)
print(ans[s])

Solution (Python):
from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    dist[n-1] = calc(arr, n-2, n-1)
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

if __name__ == "__main__":
    main()

Solution (Python):
from math import sqrt
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path
def distance(x0, y0, x1, y1):
    return sqrt((x1-x0)**2 + (y1-y0)**2)

xs, ys, xt, yt, n, *XYR = map(int, open(0).read().split())
P = [(xs, ys, 0), (xt, yt, 0)] + list(zip(XYR[::3], XYR[1::3], XYR[2::3]))

edges = np.zeros((n+2, n+2))
for i in range(n+1):
    for j in range(i+1, n+2):
        dist = distance(P[i][0], P[i][1], P[j][0], P[j][1])
        dist = max(dist - P[i][2] - P[j][2], 0.0)
        edges[i, j] = edges[j, i] = dist

G = csgraph_from_dense(edges, null_value=-1)
print(shortest_path(G, indices=0)[1])

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)


from math import sqrt
from heapq import heappush,heappop

def pdist(x1,y1,x2,y2):
    return sqrt((x2-x1)**2+(y2-y1)**2)

xs,ys,xt,yt = inm()
n = inn()
cir = []
for i in range(n):
    x,y,r = inm()
    cir.append((x,y,r))
dst = [[0]*(n+2) for i in range(n+2)]
dst[n][n+1] = dst[n+1][n] = pdist(xs,ys,xt,yt)
for i in range(n):
    x,y,r = cir[i]
    dst[n][i] = dst[i][n] = max(0.0,pdist(xs,ys,x,y)-r)
    dst[n+1][i] = dst[i][n+1] = max(0.0,pdist(xt,yt,x,y)-r)
    for j in range(i+1,n):
        xx,yy,rr = cir[j]
        dst[j][i] = dst[i][j] = \
          max(0.0,pdist(xx,yy,x,y)-rr-r)

if False and DBG:
    for i in range(n+2):
        ddprint(dst[i])

cost = [float(BIG)]*(n+2)
q = [(0.0,n)]
while len(q)>0:
    d,p = heappop(q)
    
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in range(n+2):
        newdist = d+dst[p][v]
        if v!=p and newdist<cost[v]:
            heappush(q,(newdist, v))

print(cost[n+1])

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

v = [(xs,ys,0),(xt,yt,0)]
for i in range(n):
    x,y,r = map(int,input().split())
    v.append((x,y,r))
path = [[] for i in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        l = max(0, ((v[i][0] - v[j][0])**2 + (v[i][1] - v[j][1])**2)**0.5 - v[i][2] - v[j][2])
        path[i].append((j,l))
        path[j].append((i,l))

import heapq
def Dijkstra(edge,start,v):
    d = [float('inf')]*v
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        if dist > d[p]:continue
        for to,cost in edge[p]:
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

d = Dijkstra(path, 0, n+2)
print(d[1])

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

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


"""
d: 隣接行列に対する Dijkstra
O(N^2)
"""
def Dijkstra_matrix(d,start):
    n = len(d)
    
    INF = float("inf")
    dist = d[start][:] 

    used = [0]*n 
    used[start] = 1
    for _ in range(n-1):
        d0  = INF
        idx = -1
        for i in range(n):
            if not used[i] and dist[i] < d0:
                idx = i
                d0  = dist[i]
        if idx == -1:
            return dist
        else:
            used[idx] = 1
            for j in range(n):
                if not used[j] and dist[j] > dist[idx]+d[idx][j]:
                    dist[j] = dist[idx]+d[idx][j]
    return dist

from math import hypot
d = [[max(0.0,hypot((xi-xj),(yi-yj))-ri-rj) for xj,yj,rj in xyr] for xi,yi,ri in xyr]


dist = Dijkstra_matrix(d,n)
print(dist[-1])

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

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


from heapq import *
def dijkstra(d,s0):
    n = len(d)
    INF = float("inf") 
    dist = [INF]*(n) 
    
    dist[s0] = 0.0
    res = d[s0][:]
    res[s0] = INF
    for _ in range(n-1):
        idx = min(range(n),key = lambda i: res[i])
        r = dist[idx] = res[idx]
        res[idx] = INF
        for j in range(n):
            if res[j] != INF:
                res[j] = min(res[j],r+d[idx][j])
        
        
    return dist

from math import hypot
d = [[max(0.0,hypot((xi-xj),(yi-yj))-ri-rj) for xj,yj,rj in xyr] for xi,yi,ri in xyr]


dist = dijkstra(d,n)
print(dist[-1])

Solution (Python):
XS,YS,XT,YT=map(int,input().split())
N=int(input())
V=[[XS,YS,0],[XT,YT,0]]
for i in range(N):
  V.append(list(map(int,input().split())))
INF=10**12
G=[[INF]*len(V) for i in range(len(V))]
def d(a,b):
  return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
for i in range(len(V)):
  G[i][i]=0
  for j in range(len(V)):
    G[i][j]=max(0,d(V[i][:2],V[j][:2])-V[i][2]-V[j][2])
D=[0]*len(V)
U=[0]*len(V)
def ijk(s):
  global D,U,G,V,INF
  for i in range(len(V)):
    D[i]=INF
    U[i]=False
  D[s]=0
  v=0
  while True:
    v=-1
    for i in range(len(V)):
      if not(U[i]) and (v==-1 or D[i]<D[v]):
        v=i
    if v==-1:
      break
    U[v]=True
    for i in range(len(V)):
      D[i]=min(D[i],D[v]+G[v][i])

ijk(0)
print(D[1])

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from heapq import heapify,heappop,heappush
def dijkstra(G,s = 0): 
    n = len(G)
    dist = [INF] * n
    dist[s] = 0
    q = [(0,s)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for e,cost in G[v]:
            if dist[e] > dist[v] + cost:
                dist[e] = dist[v] + cost
                heappush(q,(dist[e],e))
    return dist

from math import hypot
def main():
    sy,sx,gy,gx = map(int,input().split())
    N = int(input())
    circles = [(sy,sx,0)] + [tuple(map(int,input().split())) for _ in range(N)] + [(gy,gx,0)]
    N += 2

    G = [[] for _ in range(N)]
    for i in range(N):
        x,y,z = circles[i]
        for j in range(i + 1,N):
            p,q,r = circles[j]
            d = max(0,hypot(x - p,y - q) - z - r)
            G[i].append((j,d))
            G[j].append((i,d))
    
    dist = dijkstra(G)
    ans = dist[-1]
    print(ans)
if __name__ == '__main__':
    main()