When we enter a barrier, we can move freely inside of this barrier. If we want to go to another barrier from a barrier then we can travel the smallest distance between them, that is max(0, dist(c1, c2) — r1 — r2). We can also consider the start/end as barriers of radius 0. Now do dijkstra in O(N^2) and be happy.

GOOGLE TRANSLATED VERSION OF EDITORIAL (UNDERSTANDABLE):

For simplicity, assume that a barrier of radius 0 is also placed at the starting point $$$(x_s, y_s)$$$ and the end point $$$(x_t ,y_t )$$$.
The start point and end point will be located at the center of each barrier.
When seeking the optimum route from the start point to the end point, Snuke moves only on the line segment connecting the centers of the barriers.

It turns out that you can make the assumption because when moving from one barrier boundary to another.
Is best to move on a line connecting the centers of those barriers, and when moving inside a barrier.
Is not lost even if it goes through the center of the barrier once.

Therefore, consider a graph in which edges are set between all points with the center of each barrier as the vertex, and solve the shortest path problem of this graph.
The cost of the edge connecting the centers of barriers $$$i,j$$$ is $$$w_{ij}$$$.

$$$w_{ij} = \max ( 0,\sqrt{(x i − x j )^2 + (y i − y j )^2} − (r_i + r_j ) ) $$$

It is a shortest path problem with all edge costs nonnegative and can be solved by the Dijkstra method.
The amount of calculation is $$$O(N^2)$$$. However, depending on the implementation, there are cases in which the path that directly moves from the start point to the end point is overlooked. Please be careful.

Once you are inside a circle, you can move to any point inside it with no cost. The cost is just to jump from a circle to another one that doesn’t intersect with it. So the problem now is to compute the minimum distance from a circle to another one (by traveling through other circles). The minimum distance from a circle centered at $$$P_0$$$ with radius $$$r_0$$$ to a circle centered at $$$P_1$$$ with radius $$$r_1$$$ is $$$dist(P_0, P_1) - r_0 - r_1$$$ if the don’t intersect, otherwise the cost is $$$0$$$. So perform dijkstra algorithm and done. Since this graph is dense, it’s better option using $$$O(n^2)$$$ dijkstra.