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
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """
        
        
        
        
        class Edge():
            
            
            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost
        
        def __init__(self, V,inf):
            
            self.inf=inf
            self.G = [[] for _ 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 add2(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2
            
        def shortest_path(self,s):
            
            que = [] 
            d = [self.inf] * self.V()
            
            
            
            
            d[s] = 0
            heapq.heappush(que,(0,s)) 
            
            while len(que)!=0:
                
                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)) 
            
            """
            path = []
            pos = g 
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                
                pos = prev[pos]
            path.reverse()
            
                        
            return d
    
    mod=10**9+7
    L=LI()
    N=I()
    X=[0]*(N+2)
    Y=[0]*(N+2)
    R=[0]*(N+2)
    
    X[0]=L[0]
    X[-1]=L[2]
    Y[0]=L[1]
    Y[-1]=L[3]
    
    for i in range(N):
        X[i+1],Y[i+1],R[i+1]=MI()
        
        
    djk=Dijkstra(N+2,10**20)
    
    for i in range(N+2):
        for j in range(i+1,N+2):
            diff=( (X[i]-X[j])**2 + (Y[i]-Y[j])**2)**0.5
            cost=max(diff-R[i]-R[j],0)
            djk.add2(i,j,cost)
            
    D=djk.shortest_path(0)
    print(D[-1])
    

main()

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

def main():
    xs, ys, xt, yt = map(int, my_input().split())
    N = int(my_input())
    C = [(xs, ys, 0), (xt, yt, 0)]
    C += [tuple(map(int, my_input().split())) for i in range(N)]

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


    def dijkstra(graph, start, inf=float('inf')):
        import heapq
        n = len(graph)
        distances = [inf] * n
        distances[start] = 0
        visited = [False] * n

        
        hq = [(0, start)]
        while hq:
            dist, fr = heapq.heappop(hq)
            visited[fr] = True
            if distances[fr] < dist:
                continue
            if fr == 1:
                return distances


            for to, cost in graph[fr]:
                new_dist = distances[fr] + cost
                if (visited[to]) or (distances[to] <= new_dist):
                    continue

                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

        return distances


    dist = dijkstra(G, 0)
    print(dist[1])


if __name__ == '__main__':
    main()

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

def main():
    xs, ys, xt, yt = map(int, my_input().split())
    N = int(my_input())
    C = [(xs, ys, 0), (xt, yt, 0)]
    C += [tuple(map(int, my_input().split())) for i in range(N)]

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


    def dijkstra(graph, start, inf=float('inf')):
        import heapq
        n = len(graph)
        distances = [inf] * n
        distances[start] = 0
        visited = [False] * n

        
        hq = [(0, start)]
        while hq:
            dist, fr = heapq.heappop(hq)
            if distances[fr] < dist:
                continue
            if fr == 1:
                return distances
            visited[fr] = True

            for to, cost in graph[fr]:
                new_dist = distances[fr] + cost
                if (visited[to]) or (distances[to] <= new_dist):
                    continue

                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

        return distances


    dist = dijkstra(G, 0)
    print(dist[1])


if __name__ == '__main__':
    main()

Solution (Python):

import math
import heapq

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

d = [((xs, ys), 0, 0)]


for _ in range(N):
    x, y, r = map(int, input().split())
    d.append(((x, y), _+1, r))

graph = {i: [] for i in range(N+2)}

d.append(((xt, yt), N+1, 0))
for i in range(N+2):
    for j in range(i+1, N+2):
        p, point, rad = d[i]
        q, point2, rad2 = d[j]
        D = math.hypot(p[0]-q[0], p[1]-q[1])
        if D > (rad+rad2):
            graph[i].append((D-rad-rad2, j))
            graph[j].append((D-rad-rad2, i))
        else:
            graph[i].append((0, j))
            graph[j].append((0, i))


def dijkstra(s, graph):
    n = len(graph)
    dist = [float("inf") for i in range(n+1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    heapq.heappush(pq, (0, s))
    while pq:
        mini_dis, node = heapq.heappop(pq)
        if dist[node] < mini_dis:
            continue
        for w, point in graph[node]:
            if dist[point] < w:
                continue
            newlen = dist[node]+w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen
    return dist

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

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

sx,sy,gx,gy=map(int,input().split())
n=int(input())
arr=[[sx,sy,0]]+[list(map(int,input().split())) for _ in range(n)]+[[gx,gy,0]]
g=[[-1]*(n+2) for _ in range(n+2)]
for i in range(n+2):
  x1,y1,r1=arr[i]
  for j in range(n+2):
    x2,y2,r2=arr[j]
    g[i][j]=max(0.0,((x1-x2)**2+(y1-y2)**2)**0.5-(r1+r2))
g=csgraph_from_dense(g,null_value=-1)
ans=((sx-gx)**2+(sy-gy)**2)**0.5
print(min(ans,dijkstra(g,indices=0)[n+1]))

Solution (Python):
import heapq

def dijkstra(s):
    inf = pow(10, 10)
    dist = [inf] * (n + 2)
    dist[s] = 0
    c = [0] * (n + 2)
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist[n + 1]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
s.insert(0, [xs, ys, 0])
s.append([xt, yt, 0])
G = [[] for _ in range(n + 2)]
for i in range(n + 2):
    for j in range(n + 2):
        if not i == j:
            G[i].append([j, max(0, (pow(s[i][0] - s[j][0], 2) + pow(s[i][1] - s[j][1], 2)) ** (1 / 2) - s[i][2] - s[j][2])])
ans = dijkstra(0)
print(ans)

Solution (Python):
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
xs,ys,xg,yg = map(int, input().split())
N = int(input())
xyr = [(xs,ys,0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg,yg,0))
graph = [[0] * (N+2) for _ in range(N+2)]

max_val = 10**9

for i in range(N+2):
    graph[i][i] = max_val

for i in range(N+2):
    for j in range(i+1,N+2):
        x1,y1,r1 = xyr[i]
        x2,y2,r2 = xyr[j]
        d = max(0, ((x1-x2)**2 + (y1-y2)**2) ** 0.5 - r1 - r2)
        graph[i][j] = graph[j][i] = d

g = csgraph_from_dense(graph,null_value=max_val)
print(dijkstra(g,indices=0)[-1])

Solution (Python):
def main():
    from math import hypot
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

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

    def dist(p1, p2):
        d = hypot(p1[0] - p2[0], p1[1] - p2[1])
        return max(0, d - (p1[2] + p2[2]))

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

    adj = [[inf] * (N + 2) for _ in range(N + 2)]

    for i, p1 in enumerate(ps):
        for j, p2 in enumerate(ps):
            if i <= j: break  
            adj[i][j] = adj[j][i] = dist(p1, p2)

    def dijkstra(s):
        dist = [inf] * (N + 2)
        dist[s] = 0
        det = [0] * (N + 2)

        c, v = 0, s
        det[s] = 1
        for _ in range(N + 1):
            for u, dc in enumerate(adj[v]):
                nc = c + dc
                if dist[u] <= nc: continue
                dist[u] = nc

            c, v = -1, -1
            for u, d in enumerate(dist):
                if det[u]: continue
                if ~v and c <= d: continue
                c, v = d, u
            det[v] = 1

        return dist

    print(dijkstra(s=0)[N + 1])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from math import hypot
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

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

    def dist(p1, p2):
        d = hypot(p1[0] - p2[0], p1[1] - p2[1])
        return max(0, d - (p1[2] + p2[2]))

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

    adj = [[inf] * (N + 2) for _ in range(N + 2)]

    for i, p1 in enumerate(ps):
        for j, p2 in enumerate(ps):
            if i <= j: break  
            adj[i][j] = adj[j][i] = dist(p1, p2)

    def dijkstra(s):
        dist = [inf] * (N + 2)
        dist[s] = 0
        det = [0] * (N + 2)

        c, v = 0, s
        det[s] = 1
        while True:
            for u, dc in enumerate(adj[v]):
                nc = c + dc
                if dist[u] <= nc: continue
                dist[u] = nc

            c, v = -1, -1
            for u, d in enumerate(dist):
                if det[u]: continue
                if ~v and c <= d: continue
                c, v = d, u
            if not (~v): break
            det[v] = 1

        return dist

    print(dijkstra(s=0)[N + 1])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from math import hypot
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

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

    def dist(p1, p2):
        d = hypot(p1[0] - p2[0], p1[1] - p2[1])
        return max(0, d - (p1[2] + p2[2]))

    s = (xs, ys, 0, 0)
    g = (xt, yt, 0, N - 1)
    ps = [s, g]  
    adj = [[inf] * N for _ in range(N)]
    adj[0][N - 1] = adj[N - 1][0] = dist(s, g)
    for idx1 in range(1, N - 1):
        *p1, = map(int, input().split())  
        p1.append(idx1)
        for *p2, idx2 in ps:
            d = dist(p1, p2)
            adj[idx1][idx2] = adj[idx2][idx1] = d
        ps.append(p1)

    def dijkstra(s):
        from heapq import heappop, heappush

        dist = [inf] * N

        h = [(0, s)]  
        dist[s] = 0

        while h:
            c, v = heappop(h)
            if dist[v] < c: continue

            for u, dc in enumerate(adj[v]):
                nc = c + dc
                if dist[u] <= nc: continue
                dist[u] = nc
                heappush(h, (nc, u))

        return dist

    print(dijkstra(s=0)[N - 1])


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop, heappush, heapify
from collections import deque

class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        prev = [None for _ in range(self.n)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    prev[adj] = node
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

def dist(p, q):
    px, py = p
    qx, qy = q
    return ((px - qx)**2 + (py - qy)**2)**0.5

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

N = int(input())

barrier = [tuple(map(int, input().split())) for _ in range(N)]
edge = []

edge.append((0, N + 1, dist(s, t)))

for i in range(N):
    xi, yi, ri = barrier[i]
    pi = (xi, yi)
    d = max(dist(s, pi) - ri, 0)
    edge.append((0, i + 1, d))

for i in range(N):
    xi, yi, ri = barrier[i]
    pi = (xi, yi)
    d = max(dist(t, pi) - ri, 0)
    edge.append((N + 1, i + 1, d))

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

g = Graph(N + 2, edge, 0)

print(g.dijkstra(0)[N + 1])

Solution (Python):

import math
import heapq

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

d = [((xs, ys), 0, 0)]


for _ in range(N):
    x, y, r = map(int, input().split())
    d.append(((x, y), _+1, r))

graph = {i: [] for i in range(N+2)}

d.append(((xt, yt), N+1, 0))
for i in range(N+2):
    for j in range(i+1, N+2):
        p, point, rad = d[i]
        q, point2, rad2 = d[j]
        D = math.hypot(p[0]-q[0], p[1]-q[1])
        if D > (rad+rad2):
            graph[i].append((D-rad-rad2, j))
            graph[j].append((D-rad-rad2, i))
        else:
            graph[i].append((0, j))
            graph[j].append((0, i))


def dijkstra(s, graph):
    n = len(graph)
    dist = [float("inf") for i in range(n+1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    heapq.heappush(pq, (0, s))
    while pq:
        mini_dis, node = heapq.heappop(pq)
        if dist[node] < mini_dis:
            continue
        for w, point in graph[node]:
            if dist[point] < w:
                continue
            newlen = dist[node]+w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen
    return dist

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

Solution (Python):
xs,ys,xt,yt=map(int,input().split())
N=int(input())
import numpy as np
XYR=np.empty((N+2,3),dtype=np.float64)
XYR[1:-1,:]=np.array([input().split() for i in range(N)])
XYR[0,:]=xs,ys,0
XYR[-1,:]=xt,yt,0
X,Y,R=XYR.T
c=np.maximum(0,np.sqrt(np.square(X[None,:]-X[:,None])+np.square(Y[None,:]-Y[:,None]))-R[None,:]-R[:,None])
c[range(N+2),range(N+2)]=-1
from scipy.sparse import*
g=csgraph.csgraph_from_dense(c,null_value=-1)
print(csgraph.dijkstra(g,indices=0)[-1])

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

def main():
    x_s, y_s, x_t, y_t = map(int, readline().split())
    A = np.array([[x_s, y_s, 0],
                  [x_t, y_t, 0]], dtype=np.int)
    
    N = int(readline())
    B = np.array(read().split(), dtype=np.int).reshape(-1, 3)
    XY, R = np.hsplit(np.concatenate((A, B)), [2])
    
    d = np.expand_dims(XY, axis=1) - np.expand_dims(XY, axis=0)
    d = np.sqrt(np.sum(np.square(d), axis=-1))
    d -= R + R.reshape(1, -1)
    d = np.maximum(d, 0)
    np.fill_diagonal(d, -1)
    d = csgraph_from_dense(d, null_value=-1)
     
    ans = dijkstra(d, indices=0)[1]
    print(ans)


if __name__ == "__main__":
    main()

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

def main():
    x_s, y_s, x_t, y_t = map(int, readline().split())
    A = np.array([[x_s, y_s, 0],
                  [x_t, y_t, 0]], dtype=np.int)
    
    N = int(readline())
    B = np.array(read().split(), dtype=np.int).reshape(-1, 3)
    XY, R = np.hsplit(np.concatenate((A, B)), [2])
    
    d = np.expand_dims(XY, axis=1) - np.expand_dims(XY, axis=0)
    d = np.sqrt(np.sum(d ** 2, axis=-1))
    d -= R + R.reshape(1, -1)
    d = np.maximum(d, 0)
    np.fill_diagonal(d, -1)
    d = csgraph_from_dense(d, null_value=-1)
     
    ans = dijkstra(d, indices=0)[1]
    print(ans)


if __name__ == "__main__":
    main()

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

INF = 10**15

def dijkstra(E, s, g):
    d = [INF] * len(E)
    d[0] = 0

    queue = []
    heappush(queue, (0, s))

    while queue:
        dist_v, v = heappop(queue)
        if dist_v > d[v]:
            continue
        
        for e, w in E[v]:
            tmp = d[v] + w
            if tmp < d[e]:
                d[e] = tmp
                heappush(queue, (tmp, e))
    
    return d[g]


def main():
    x_s, y_s, x_t, y_t = map(int, readline().split())
    N,*xyr = map(int, read().split())

    XYR = []
    XYR.append((x_s, y_s, 0))
    XYR.append((x_t, y_t, 0))
    for x, y, r in zip(*[iter(xyr)]*3):
        XYR.append((x, y, r))
    
    E = [[] for _ in range(N+2)]
    for i in range(N+1):
        x_i, y_i, r_i = XYR[i]
        for j in range(i+1, N+2):
            x_j, y_j, r_j = XYR[j]
            d = sqrt((x_i - x_j)**2 + (y_i - y_j)**2)
            d -= r_i + r_j
            d = max(0, d)
            E[i].append((j, d))
            E[j].append((i, d))

    ans = dijkstra(E, 0, 1)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappush,heappop,heapify
INF=10**30

def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for c,v in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist

sx,sy,gx,gy=map(int,input().split())
N=int(input())
X,Y,R=[sx,gx],[sy,gy],[0,0]
for i in range(N):
    t,m,p=map(int,input().split())
    X.append(t);Y.append(m);R.append(p)
G=[[] for i in range(N+2)]
for i in range(N+2):
    for j in range(i):
        d=max(0,((X[i]-X[j])**2+(Y[i]-Y[j])**2)**0.5-R[i]-R[j])
        G[i].append((d,j))
        G[j].append((d,i))
dist=dijkstra(G,0,N+2)
print(dist[1])

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

d = [[0]*(N+3) for _ in range(N+3)]
for i in range(1,N+3):
  d[i][i] = 0

for i in range(1,N+3):
  for j in range(i+1,N+3):
    sa = (l[i][0]-l[j][0])**2 + (l[i][1]-l[j][1])**2
    kyori = max(0,sa**(1/2)-l[i][2]-l[j][2])
    d[i][j] = kyori
    d[j][i] = kyori

md = [float("inf")]*(N+3)
h = [i for i in range(1,N+3)]
for i in range(1,N+3):
  md[i]=d[1][i]
seen = [False]*(N+3)
seen[1] = True
while True:
  
  v = -1
  for i in h:
    if seen[i] == False and v == -1:
      v = i
    elif seen[i] == False and md[i] < md[v]:
      v = i
  if v == -1:
    break
  seen[v] = True
  for j in range(1,N+3):
    md[j] = min(md[j],md[v]+d[v][j])
print(md[2])

Solution (Python):
import heapq
INFTY = 10**10
def f(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
xs,ys,xt,yt = map(int,input().split())
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
A.insert(0,[xs,ys,0])
A.append([xt,yt,0])
dist = [INFTY for _ in range(N+2)]
hist = [0 for _ in range(N+2)]
heap = [(0,0)]
dist[0]=0
hist[0]=1
while heap:
    d,x = heapq.heappop(heap)
    if dist[x]<d:continue
    hist[x]=1
    for i in range(N+2):
        if hist[i]==0:
            if dist[i]>d+max(f(A[x][:2],A[i][:2])-(A[x][2]+A[i][2]),0):
                dist[i]=d+max(f(A[x][:2],A[i][:2])-(A[x][2]+A[i][2]),0)
                heapq.heappush(heap,(dist[i],i))
print(dist[N+1])

Solution (Python):
import sys

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


def resolve():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    XYR = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(n):
        x, y, r = map(int, input().split())
        XYR.append([x, y, r])

    cost = [[0] * (n + 2) for _ in range(n + 2)]
    for i in range(n + 2):
        x1, y1, r1 = XYR[i]
        for j in range(n + 2):
            x2, y2, r2 = XYR[j]
            dist = max(0, pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5) - (r1 + r2))
            cost[i][j] = cost[j][i] = dist

    def dijkstra(s):
        
        
        d = [f_inf] * (n + 2)
        used = [False] * (n + 2)
        d[s] = 0

        while True:
            v = -1
            
            for k in range(n + 2):
                if (not used[k]) and (v == -1):
                    v = k
                elif (not used[k]) and d[k] < d[v]:
                    v = k
            if v == -1:
                break
            used[v] = True

            for m in range(n + 2):
                d[m] = min(d[m], d[v] + cost[v][m])
        return d

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


if __name__ == '__main__':
    resolve()

Solution (Python):
from heapq import heappush, heappop

sX, sY, tX, tY = map(int, input().split())
N = int(input())

XYR = [tuple(map(int, input().split())) for _ in range(N)] + [(sX, sY, 0), (tX, tY, 0)]
S, T = N, N + 1
N += 2

edges = [[] for _ in range(N)]
for i, (x, y, r) in enumerate(XYR):
    for j, (u, v, w) in enumerate(XYR[i + 1:], start=i + 1):
        dist = max(0, ((x - u)**2 + (y - v)**2)**0.5 - (r + w))
        edges[i].append((j, dist))
        edges[j].append((i, dist))

minDist = [10**18] * N
minDist[S] = 0
que = [(0, S)]
while que:
    dist, now = heappop(que)
    if minDist[now] < dist:
        continue
    for to, cost in edges[now]:
        d = dist + cost
        if minDist[to] > d:
            minDist[to] = d
            heappush(que, (d, to))
print(minDist[T])

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



A, B, C, D = map(int, input().split())
N = int(input())

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

X = [0]*N
Y = [0]*N
R = [0]*N
for i in range(N):
    X[i],Y[i],R[i] = map(int, input().split())
d[0][-1] = ((C-A)**2+(D-B)**2)**0.5
d[-1][0] = ((C-A)**2+(D-B)**2)**0.5
for i in range(1,N+1):
    d_s = max(0,((X[i-1]-A)**2+(Y[i-1]-B)**2)**0.5-R[i-1])
    d_e = max(0,((X[i-1]-C)**2+(Y[i-1]-D)**2)**0.5-R[i-1])
    d[0][i],d[i][0] = d_s,d_s
    d[N+1][i],d[i][N+1] = d_e,d_e
    for j in range(1,N+1):
        d[i][j] = max(((X[i-1]-X[j-1])**2+(Y[i-1]-Y[j-1])**2)**0.5-R[i-1]-R[j-1],0)
s = 0 
d = dijkstra_heap(N+2,s,d)
print(d[-1])

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

    INF = 10 ** 10

    from math import sqrt

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

    N = int(input())
    XYR = [tuple(map(int, input().split())) for _ in range(N)]

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

    def diff1(i, j):
        tmp = (XYR[i][0] - XYR[j][0]) ** 2 + (XYR[i][1] - XYR[j][1]) ** 2
        R = XYR[i][2] + XYR[j][2]
        return max(0, sqrt(tmp) - R)

    for i in range(N - 1):
        for j in range(i + 1, N):
            tmp = diff1(i, j)
            G[i].append((tmp, j))
            G[j].append((tmp, i))

    def diff2(x, y, i):
        tmp = (x - XYR[i][0]) ** 2 + (y - XYR[i][1]) ** 2
        R = XYR[i][2]
        return max(0, sqrt(tmp) - R)

    for i in range(N):
        tmp = diff2(xs, ys, i)
        G[N].append((tmp, i))
        G[i].append((tmp, N))


    for i in range(N):
        tmp = diff2(xg, yg, i)
        G[N + 1].append((tmp, i))
        G[i].append((tmp, N + 1))

    tmp = (xs - xg) ** 2 + (ys - yg) ** 2
    G[N].append((sqrt(tmp), N + 1))
    G[N + 1].append((sqrt(tmp), N))

    d = [INF] * (N + 2) 

    def dijksrea(s): 
        from heapq import heappop, heappush
        d[s] = 0 
        pque = []
        heappush(pque, (0, s)) 

        while pque: 
            p = heappop(pque) 
            v = p[1] 
            if d[v] < p[0]: 
                continue
            for i in range(len(G[v])): 
                e = G[v][i]
                if d[e[1]] > d[v] + e[0]: 
                    d[e[1]] = d[v] + e[0]
                    heappush(pque, (d[e[1]], e[1])) 

    dijksrea(N)
    print (d[N + 1])

    

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sx,sy,tx,ty=map(int,input().split())
n=int(input())
p=[(sx,sy,0)]
for _ in range(n):
  x,y,r=map(int,input().split())
  p.append((x,y,r))
p.append((tx,ty,0))
n+=2
edge=[[]for _ in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    sx,sy,sr=p[i]
    tx,ty,tr=p[j]
    t=(abs(sx-tx)**2+abs(sy-ty)**2)**0.5
    c=max(0,t-(sr+tr))
    edge[i].append((j,c))
    edge[j].append((i,c))
from heapq import heappop,heappush
inf=10**20
ans=[inf]*n
ans[0]=0
root=[-1]*n
h=[(0,0)]
while h:
  c,v=heappop(h)
  if ans[v]<c:continue
  for u,t in edge[v]:
    if c+t<ans[u]:
      ans[u]=c+t
      root[u]=v
      heappush(h,(c+t,u))
print(ans[n-1])

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
xs,ys,xt,yt = map(int,input().split())
N=int(input())
xyr = [tuple(map(int,input().split())) for _ in range(N)]
xyr.append((xs,ys,0))
xyr.append((xt,yt,0))
b = [[-1]*(N+2) for _ in range(N+2)]
for i in range(N+2):
    x1, y1, r1 = xyr[i]
    for j in range(i+1,N+2):
        x2,y2,r2 = xyr[j]
        r = max(0, ((x1-x2)**2+(y1-y2)**2)**0.5-(r1+r2))
        b[i][j] = r
        b[j][i] = r
Graph = csgraph_from_dense(b, null_value=-1)
start = N
end = N+1
print(dijkstra(Graph, indices=start)[end])

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

xyrlist=[]
for _ in range(N):
  x,y,r=map(int,input().split())
  xyrlist.append((x,y,r))
  
graph=[[] for _ in range(N+2)]

graph[0].append((N+1,math.sqrt((xt-xs)**2+(yt-ys)**2)))


for i in range(N):
  xi,yi,ri=xyrlist[i]
  if (xs-xi)**2+(ys-yi)**2<=ri**2:
    graph[0].append((i+1,0))
  else:
    graph[0].append((i+1,math.sqrt((xs-xi)**2+(ys-yi)**2)-ri))


for i in range(N):
  xi,yi,ri=xyrlist[i]
  for j in range(i+1,N):
    xj,yj,rj=xyrlist[j]
    if (xj-xi)**2+(yj-yi)**2<=(ri+rj)**2:
      graph[i+1].append((j+1,0))
      graph[j+1].append((i+1,0))
    else:
      graph[i+1].append((j+1,math.sqrt((xj-xi)**2+(yj-yi)**2)-ri-rj))
      graph[j+1].append((i+1,math.sqrt((xj-xi)**2+(yj-yi)**2)-ri-rj))


for i in range(N):
  xi,yi,ri=xyrlist[i]
  if (xt-xi)**2+(yt-yi)**2<=ri**2:
    graph[i+1].append((N+1,0))
  else:
    graph[i+1].append((N+1,math.sqrt((xt-xi)**2+(yt-yi)**2)-ri))

    
import heapq
def dijkstra_heap(s):
  
  dist=[float("inf")]*size_v
  used=[False]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v))

  while hq_edge:
    min_w,min_v=heapq.heappop(hq_edge)
    
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    
    for v,w in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v))

  return dist

size_v=N+2
dist=dijkstra_heap(0)

print(dist[N+1])

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

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

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

row = [0]
col = [1]
data = [dist(xs, ys, xt, yt)]
for i, (xi, yi, ri) in enumerate(xyr, 2):
  d1 = max(0, dist(xi, yi, xs, ys) - ri)
  d2 = max(0, dist(xi, yi, xt, yt) - ri)
  row.extend([0, 1])
  col.extend([i, i])
  data.extend([d1, d2])
  for j in range(i-1, N):
    xj, yj, rj = xyr[j]
    dij = max(0, dist(xi, yi, xj, yj) - ri - rj)
    row.append(i)
    col.append(j+2)
    data.append(dij)

graph = csr_matrix((data, (row, col)), shape=(N+2, N+2))
dist = dijkstra(graph, directed=False, indices=0)
print(dist[1])