ABC244F - Shortest Good Path - 競プロはじめました

考え方
回答例

考え方

ある文字列$S$に関する良いパス$A$がわかっていたとすると，そのパスの最後の頂点から隣の頂点に遷移してできたパス$A^{\prime}$は対応する文字列$S^{\prime}$に関する良いパス（の候補）である．

最短距離が確定した「（文字列，終点）の組」をキューから順に取り出し，隣接頂点をみていく．隣接頂点を終点に加えた文字列をまだ見ていないなら，その「（文字列，終点）の組」の最短距離が確定する．

初期状態では，1点だけからなる文字列の最短距離が1に確定しているので，これをキューに入れる．

※グラフでなければ「$S$を全通り生成してbit全探索」みたいなことを想像するが，辺をたどって遷移しなければならないのではじめに$S$を決めてから処理するのは難しい．よって，辺をたどって$S$を生成していくことになる．

回答例

from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x) - 1, input().split())
    G[u].append(v)
    G[v].append(u)

d = [[1 << 60] * N for _ in range(1 << N)]
q = deque()
for i in range(N):
    d[1 << i][i] = 1
    q.append((1 << i, i))

while q:
    S, cur = q.popleft()
    for chi in G[cur]:
        S2 = S ^ (1 << chi)
        if d[S2][chi] < (1 << 60): continue
        d[S2][chi] = d[S][cur] + 1
        q.append((S2, chi))

ans = sum(min(d[i]) for i in range(1, 1 << N))
print(ans)

【参考】
【解説実況】ABC244 F問題【かつっぱ】 - YouTube
Submission #30289528 - AtCoder Beginner Contest 244