概要

この問題は、すべての町を少なくとも1回訪問して出発点に戻る最短経路（巡回セールスマン問題）を求める問題です。

考察

• すべての町を訪問して戻る経路は、同じ町や道路を複数回通ることが許されていますが、直接すべての経路を列挙すると計算量が膨大になります（\(O(N!)\)）。
• グラフが完全グラフではないため、すべての町の組の間で直接道路が存在するわけではありません。そのため、まず全点間の最短距離を求める必要があります。
• 制約が \(N \leq 15\) と小さいため、ビットDP（動的計画法）を用いて効率的に解くことができます。ビットDPでは、訪問済みの町の集合と現在位置を状態として持ち、最短移動時間を計算します。

アルゴリズム

1. 全点間最短距離の計算: ワーシャル-フロイド法を用いて、すべての町の組の間の最短移動時間を計算します。これにより、直接道路がなくても迂回して移動できる場合に対応します。
2. ビットDPの初期化:
   • dp[s][i] を、訪問済みの町の集合が s（ビットマスク）で現在地が町 i であるときの最小移動時間と定義します。
   • 初期状態は出発点である町0のみ訪問済みなので、dp[1][0] = 0 とします。
3. DPの更新:
   • 現在の状態 (s, i) から、まだ訪問していない町 j に移動する場合を考え、dp[ns][j] = min(dp[ns][j], dp[s][i] + dist[i][j]) で更新します（ns = s | (1<<j)）。
4. 答えの計算:
   • すべての町を訪問した状態（s = (1<<n)-1）から、町0に戻る経路を考慮し、min(dp[full][i] + dist[i][0]) を求めます。

計算量

• 時間計算量: \(O(N^3 + 2^N \cdot N^2)\)
  • ワーシャル-フロイド法: \(O(N^3)\)
  • ビットDP: 状態数 \(O(2^N \cdot N)\)、各状態からの遷移 \(O(N)\)
• 空間計算量: \(O(2^N \cdot N)\)

実装のポイント

• ワーシャル-フロイド法を実行する前に、自己ループ（同じ町への移動）は0に、それ以外は大きな値（INF）で初期化します。

• 道路の入力では、同じ町の組に複数の道路が存在する可能性があるため、最小の重みのみを採用します。

• DPテーブルの初期化では、到達不可能な状態を INF で表現します。

• 最終的にすべての町を訪問した後、町0に戻れるかどうか（dist[i][0] != INF）を確認する必要があります。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    m = int(data[1])
    INF = 10**18
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        
    index = 2
    for i in range(m):
        u = int(data[index]); v = int(data[index+1]); w = int(data[index+2])
        index += 3
        u -= 1
        v -= 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
            
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    
    dp = [[INF] * n for _ in range(1<<n)]
    dp[1][0] = 0
    
    for s in range(1<<n):
        for i in range(n):
            if dp[s][i] == INF:
                continue
            for j in range(n):
                if s & (1<<j):
                    continue
                if dist[i][j] == INF:
                    continue
                ns = s | (1<<j)
                if dp[ns][j] > dp[s][i] + dist[i][j]:
                    dp[ns][j] = dp[s][i] + dist[i][j]
                    
    ans = INF
    full = (1<<n) - 1
    for i in range(n):
        if dp[full][i] != INF and dist[i][0] != INF:
            total = dp[full][i] + dist[i][0]
            if total < ans:
                ans = total
                
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

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