PAST1J

https://gyazo.com/35e2c2626e0ea16ae8009726cef684e2

Thoughts.

Since there is a transit point, find the distance from the Y intersection to the three points and choose the one with the smallest sum.

O(V^2logV), so we can make it in time.

Official Explanation

AC

Construct a graph and use Dijkstra method to find one_to_all distances from three endpoints

This counts three intersections, so subtract two.

Answer the minimum cost of the Y-junction obtained

code:python

def solve(H, W, AS):

from collections import defaultdict

edges = defaultdict(dict)

for x in range(W):

for y in range(H):

pos = y * W + x

if x < W - 1:

if x > 0:

if y < H - 1:

if y > 0:

d1 = one_to_all(W - 1, H * W, edges)

d2 = one_to_all(W * (H - 1), H * W, edges)

d3 = one_to_all(W * H - 1, H * W, edges)

INF = 9223372036854775807

ret = INF

for x in range(W):

for y in range(H):

pos = y * W + x

if v < ret:

ret = v

return ret

---