概要

この問題は、すべての町を少なくとも1回訪問し、最後に初期地点に戻る最短経路を求める「巡回セールスマン問題（TSP）」の変形です。

考察

この問題では、町の数 \(N\) が最大で \(15\) と小さいため、全探索的なアプローチが有効です。しかし単純にすべての順列を試すと、\(N!\) 通りとなり計算量が爆発します（例：\(15! \approx 1.3 \times 10^{12}\) でTLE）。

また、同じ町や道を複数回通って良いという条件から、直接辺でつながっていなくても最短経路で移動可能です。そのため、最初にすべての町間の最短距離を前もって求めると、その後の経路探索が楽になります。

このように、「まず最短距離を前処理しておき」「その後で効率的に経路を探索する」という2段階のアプローチが有効です。具体的には以下のように進めます： 1. Floyd-Warshall法で全点対間の最短距離を求める。 2. bitDP（ビット動的計画法）で訪問済みの町の集合と現在地を状態として、最小コストを更新していく。

さらに、すべての町に到達できない場合は -1 を出力する必要があるので、最初に連結性のチェックを行う必要があります。

アルゴリズム

ステップ1: 全点対最短距離の前処理

• グラフを隣接行列で表現し、Floyd-Warshall法により任意の2頂点間の最短距離を求めます。
• 時間計算量は \(O(N^3)\)。

ステップ2: bitDPによる巡回経路探索

• bitDPを用いて、訪問済みの町の集合をビットで管理します。
• dp[S][i] := 町の集合 \(S\) を訪問し、現在町 \(i\) にいるときの最小コスト。
• 状態数は \(2^{N-1} \times N\) （ただし、最初の町0は常に含むので残り \(N-1\) の部分集合）。
• 遷移は、現在の状態から未訪問の町に移動する場合に行われます。
• 最後に、すべての町を訪問した状態から町0に戻るコストを加えて全体の最小値を求めます。

計算量

• 時間計算量: \(O(N^3 + N^2 \cdot 2^N)\)
  • Floyd-Warshall: \(O(N^3)\)
  • bitDPの遷移: 各状態 \(S\) に対して、現在地 \(i\) と次の町 \(j\) を走査 → \(O(N \cdot 2^N \cdot N) = O(N^2 \cdot 2^N)\)
• 空間計算量: \(O(N^2 + N \cdot 2^N)\)
  • 隣接行列とDPテーブルによる。

実装のポイント

• 町の番号は1-indexedだが、内部的には0-indexedに変換して扱う（コード中では u-1, v-1）。
• bitDPの際に、最初の町（町0）は常に訪問済みとして扱い、集合 \(S\) には町1〜N-1だけを含める。
• Floyd-Warshall後、町0から他のすべての町に到達可能かチェックし、到達不能があれば -1 を出力。
• DP初期化：dp[0][0] = 0（集合空、初期位置）。
• 最終ステップで、すべての町を訪問した状態から町0に戻るコストを忘れずに足す。

## ソースコード

```python
import sys
from itertools import permutations

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    edges = []
    index = 2
    for _ in range(M):
        u = int(data[index])
        v = int(data[index+1])
        w = int(data[index+2])
        edges.append((u-1, v-1, w))
        index += 3
    
    # グラフ構築 (隣接行列)
    INF = float('inf')
    dist = [[INF]*N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
        dist[v][u] = min(dist[v][u], w)
    
    # Floyd-Warshall
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # ノード1(0-indexed)から他のノードへの最短距離をチェック
    # ただし、すべてのノードに到達可能か確認する必要がある
    reachable = True
    for i in range(N):
        if dist[0][i] == INF:
            reachable = False
            break
    if not reachable:
        print(-1)
        return
    
    # ノード集合 {1, ..., N-1} の部分集合に対するbitDP
    # dp[S][i] := 訪問済みノード集合S、現在位置i における最小コスト
    ALL = 1 << (N-1)
    dp = [[INF]*N for _ in range(ALL)]
    dp[0][0] = 0  # 最初は町0(1-indexedで1)にいる
    
    for S in range(ALL):
        for i in range(N):
            if dp[S][i] == INF:
                continue
            # 次に訪問するノードj (1-indexed -> 0-indexed: 1 to N-1 => 1 to N-1)
            for j in range(1, N):
                if (S >> (j-1)) & 1:
                    continue
                new_S = S | (1 << (j-1))
                cost = dist[i][j]
                if dp[new_S][j] > dp[S][i] + cost:
                    dp[new_S][j] = dp[S][i] + cost
    
    # 最後に町0に戻る
    result = INF
    full_set = (1 << (N-1)) - 1
    for i in range(N):
        if dp[full_set][i] != INF:
            result = min(result, dp[full_set][i] + dist[i][0])
    
    if result == INF:
        print(-1)
    else:
        print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。