概要

この問題は、指定された出発地点からすべての配達先を任意の順序で訪れて戻ってくる最短経路を求める巡回セールスマン問題の一種です。

考察

• すべての配達先を訪れる経路を全探索すると、\(K!\) 通りの順列を試す必要がありますが、\(K \leq 15\) なので最大 \(15! \approx 1.3 \times 10^{12}\) 通りとなり、単純な全探索では計算が間に合いません。
• また、同じ地点や道路を複数回通ることが許されているため、最短経路を求める際には全点対間最短経路を事前に計算しておく必要があります。
• 重要な観察として、実際に関係するのは出発地点 \(S\) と \(K\) 個の配達先のみです。他の地点は経由地としてのみ機能するため、全点対間最短経路を計算した上で、これらの重要な地点だけを抽出して巡回セールスマン問題を解くことができます。

アルゴリズム

1. ワーシャル–フロイド法: まず、全点対間最短経路を計算します。これにより、任意の2地点間の最短距離が \(O(N^3)\) で求まります。
2. 重要な地点の抽出: 出発地点 \(S\) と \(K\) 個の配達先からなる合計 \(n = K+1\) 個の地点集合を抽出します。
3. 巡回セールスマン問題 (TSP): 抽出された \(n\) 個の地点間で巡回セールスマン問題を解きます。動的計画法を用い、状態を「訪問済み地点のビットマスク」と「現在地点」で表し、\(O(2^n \cdot n^2)\) で計算します。
4. 最終的な経路の計算: すべての地点を訪問した後、出発地点 \(S\) に戻る経路のコストを加算して最小値を求めます。

計算量

• 時間計算量: \(O(N^3 + 2^n \cdot n^2)\)（\(n = K+1\)）
• 空間計算量: \(O(N^2 + 2^n \cdot n)\)

実装のポイント

• ワーシャル–フロイド法を実行する前に、自己ループ（\(i\) から \(i\) への移動）のコストを \(0\) に初期化します。

• 重要な地点の集合には重複が含まれないよう、set を使ってユニークな地点を抽出します。

• 動的計画法の初期状態では、出発地点 \(S\) のみを訪問済み（ビットマスクで対応するビットを立てる）とし、コストを \(0\) に設定します。

• 最終的に、すべての地点を訪問した状態から出発地点に戻る経路のコストを加算して最小値を求めます。

  ソースコード

def main():
    import sys
    from itertools import permutations

    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return

    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); idx += 2
    INF = 10**18
    dist = [[INF] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        dist[i][i] = 0

    for _ in range(M):
        u = int(data[idx]); v = int(data[idx+1]); w = int(data[idx+2]); idx += 3
        if w < dist[u][v]:
            dist[u][v] = w

    S = int(data[idx]); K = int(data[idx+1]); idx += 2
    T_list = [int(data[idx+i]) for i in range(K)]
    targets = [S] + T_list
    unique_nodes = sorted(set(targets))
    mapping = {}
    for i, node in enumerate(unique_nodes):
        mapping[node] = i
    n_nodes = len(unique_nodes)
    new_dist = [[INF] * n_nodes for _ in range(n_nodes)]

    for k in range(1, N+1):
        for i in range(1, N+1):
            if dist[i][k] == INF:
                continue
            for j in range(1, N+1):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    for i, u in enumerate(unique_nodes):
        for j, v in enumerate(unique_nodes):
            new_dist[i][j] = dist[u][v]

    dp = [[INF] * n_nodes for _ in range(1<<n_nodes)]
    start_index = mapping[S]
    dp[1<<start_index][start_index] = 0

    for mask in range(1<<n_nodes):
        for i in range(n_nodes):
            if dp[mask][i] == INF:
                continue
            for j in range(n_nodes):
                if mask & (1<<j):
                    continue
                new_mask = mask | (1<<j)
                cost = dp[mask][i] + new_dist[i][j]
                if cost < dp[new_mask][j]:
                    dp[new_mask][j] = cost

    full_mask = (1<<n_nodes) - 1
    ans = INF
    for i in range(n_nodes):
        if dp[full_mask][i] != INF:
            total = dp[full_mask][i] + new_dist[i][start_index]
            if total < ans:
                ans = total

    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。