PAST1J

https://gyazo.com/35e2c2626e0ea16ae8009726cef684e2

考えたこと

経由地点があるのでY字の交差点から3地点への距離を求めて和の最小なものを選ぶ

O(V^2logV)なので間に合う

公式解説

AC

グラフを構築してダイクストラ法で3つの端点からone_to_allの距離を求める

これは交差点を3回数えてるので2回分を差し引く

得られたY字路のコストの最小値を答える

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