第三回 PAST M - 行商計画問題

問題原文

atcoder.jp

解法

の制約が小さいのがポイント。
訪れたい 個の頂点について、全点間最短距離は からそれぞれBFSをすれば求められる。

これで巡回セールスマンっぽい問題になったので、あとはbitDPで解ける。

実装

枝刈りしてないけど。。。まぁいいか！

from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append(v)
    G[v].append(u)

S = int(input())
S -= 1
K = int(input())
T = list(map(lambda x: int(x) - 1, input().split()))
T = [S] + T
K += 1
A = [[float('inf')] * K for _ in range(K)]

def bfs(sn):
    distances = [float('inf')] * N
    distances[sn] = 0
    que = deque([sn])

    while que:
        n = que.pop()
        for to in G[n]:
            if distances[to] != float('inf'):
                continue
            distances[to] = distances[n] + 1
            que.appendleft(to)

    return distances

for i, sn in enumerate(T):
    distances = bfs(sn)
    for j, to in enumerate(T):
        A[i][j] = distances[to]

# dp[bs][t] := 集合bsをすでに訪れていて、最後にtを訪れているような場合の最小コスト
dp = [[float('inf')] * K for _ in range(1 << K)]
dp[1][0] = 0
for bs in range(1, 1 << K):
    for t in range(K):
        for nx in range(K):
            dp[bs | (1 << t)][nx] = min(dp[bs | (1 << t)][nx], dp[bs][t] + A[t][nx])

print(min(dp[-1]))

感想

スーパーマーケットの方が普通に苦手だった説がある。
後半３問をチャレンジ枠と捉えた時点で私は敗北していたのだ。。。