[ABC257F] Teleporter Setting を Pythonで解く

https://atcoder.jp/contests/abc257/tasks/abc257_f

考え方

移動先が決まっていないテレポーターがあるのがポイント。この未定テレポーターの処理の仕方が面白いです。下図の例 $N=9$ では、未定テレポーターを使わなければ、$1$ から $9$ への最短経路長は $8$ です。

未定テレポーターを接続したときに、最短経路長に与える影響について考えていきますが、便宜上、未定テレポーターについては、接続先へ行くことをくだり、接続先から来ることをのぼりと決めます。

未定テレポーターを使うときには、以下の3パターンがあります。
(1) 最短経路のために、未定テレポーターをのぼりで1回使う（最短距離は4）

(2) 最短経路のために、未定テレポーターをくだりで1回使う（最短距離は4）

(3) 最短経路のために、未定テレポーターをくだり のぼりの2回使う（最短距離は6）

これら3つと (0) 未定テレポーターを使わないパターンがありますが、この4つのパターンをこのまま考えるのではなく、未定テレポーターの接続先を $0$ 番として仮につくっておきます。この $0$ 番を準備することで、(0)未定テレポーターを使わない、(3)未定テレポーターをくだり のぼりの2回使う のパターンは網羅することができます。

未定テレポーターの接続先が決まったときには、この $0$ 番と接続先を移動コスト $0$ の辺でつなぐと考えることができます。

Dist_1[ $v$ ] を頂点 $1$ からの各点 $v$ の距離、Dist_N[ $v$ ] を頂点 $N$ からの各点 $v$ の距離とすると、 $0$ と $i$ は移動コスト $0$ の辺でつながっているので、Dist_1[ $0$ ] + Dist_N[ $i$ ] と Dist_1[ $i$ ] + Dist_N[ $0$ ] を考えれば良いことになります。

あとは、Dist_1[ $v$ ], Dist_N[ $v$ ] をBFS（幅優先探索）で前計算しておけば良いです。

実装メモ

from collections import deque
N,M = map(int,input().split())
E = [[] for _ in range(N+1)]
INF = 10**8

for _ in range(M):
    u,v = map(int,input().split())
    E[u].append(v)
    E[v].append(u)

スタートがsのときに、各点までの距離を求める関数を準備する。

def dist_cal(s):
    dist = [INF]*(N+1)
    dist[s] = 0
    dq = deque([[0,s]])

    while dq:
        d,t = dq.popleft()
        for u in E[t]:
            if dist[u] < INF: continue
            dist[u] = d+1
            dq.append([d+1,u])
    return dist

あとは、未定テレポーターの接続先 $i$ を変化させて、

計算	考えているパターン
Dist_1[ $N$ ]	未定テレポーターを使わない、またはくだり のぼりの2回使う
Dist_1[ $0$ ]+Dist_N[ $i$ ]	未定テレポーターをくだりで1回使う
Dist_1[ $i$ ]+Dist_N[ $0$ ]	未定テレポーターをのぼりで1回使う

の最小値をとれば良い。

Dist_1 = dist_cal(1)
Dist_N = dist_cal(N)

ans = []
for i in range(1,N+1):
    a = min(Dist_1[N], Dist_1[0]+Dist_N[i], Dist_1[i]+Dist_N[0])
    if a >= INF: a = -1
    ans.append(a)

print(*ans, sep=" ")