概要

町 \(1\) から出発して全ての町を少なくとも1回訪れ、最後に町 \(1\) に戻るための最短移動時間を求めます（不可能なら -1）。\(N \le 15\) なので、最短経路 + bitDP（巡回セールスマン型）で解きます。

考察

重要な気づき

• 「同じ町や道路を何度通ってもよい」ので、実際の移動は途中で町を何回経由しても構いません。
• そこで、任意の2町間の移動は「最短経路」で置き換えてよいです。
  つまり、元のグラフ上での最適解は「各町間の最短距離で完全グラフを作った上で、その上で全頂点を回る最短巡回路」を解けば得られます。

素朴な方法がダメな理由

• 町を訪れる順番を全探索すると \(N!\) 通りで、\(N=15\) でも \(15! \approx 1.3\times 10^{12}\) と到底間に合いません。
• また、元のグラフのまま「どの道路を通るか」まで含めて状態管理すると状態が爆発します。

解決策

1. Floyd–Warshall で全点対最短距離 \(dist[u][v]\) を計算する
   
2. 「訪問済み集合」をビットで持つ bitDP（巡回セールスマン問題の典型DP）で最小コストを求める

さらに、町1から到達不能な町が1つでもあるなら、そもそも全町訪問が不可能なので -1 とできます。

アルゴリズム

1. 全点対最短距離（Floyd–Warshall）

• \(dist[i][j]\) を「町 \(i\) から町 \(j\) への最短移動時間」として初期化します。
  • \(dist[i][i]=0\)
  • 道路があるところはその重み、ないところは \(INF\)
• Floyd–Warshall により、全ての \((i,j)\) について最短距離に更新します。

この結果、例えば「\(2 \rightarrow 5\) に直接道路がなくても、\(2 \rightarrow 3 \rightarrow 5\) が最短なら \(dist[2][5]\) はその合計」になります。
以後は「町間移動コストは \(dist\) を使う」だけでよく、途中経由の細かい経路は考えなくて済みます。

2. bitDP（訪問済み集合DP）

• \(mask\) を訪問済み集合（ビット集合）とします。ビット \(j\) が1なら町 \(j\) を訪問済み。
• \(dp[mask][i]\) を次のように定義します：

町1（0番）から出発し、集合 \(mask\) に含まれる町をすべて訪問し終えて、現在町 \(i\) にいるときの最小時間

初期状態： - 町1だけ訪問済みで町1にいる：\(dp[1<<0][0]=0\)

遷移： - \(dp[mask][i]\) から、まだ訪問していない町 \(j\) へ行く - 新しい集合 \(nmask = mask \,|\, (1<<j)\) - 更新：
\(dp[nmask][j] = \min(dp[nmask][j],\ dp[mask][i] + dist[i][j])\)

答え： - 全町訪問済み \(full = (1<<N)-1\) として、最後に町1へ戻るコストを足します： [ \min_{i} \left( dp[full][i] + dist[i][0] \right) ] - 途中で到達不能がある場合や最終的に答えが作れない場合は -1。

計算量

• 時間計算量:
  
  • Floyd–Warshall: \(O(N^3)\)
    
  • bitDP: \(O(2^N \cdot N^2)\)
    よって合計 \(O(N^3 + 2^N N^2)\)
• 空間計算量:
  
  • \(dist\): \(O(N^2)\)
    
  • \(dp\): \(O(2^N \cdot N)\)
    よって合計 \(O(N^2 + 2^N N)\)

(\(N=15\) なら \(2^{15}\cdot 15^2 \approx 7.4\) 百万程度で十分間に合います)

実装のポイント

• 最短距離が \(INF\) のままの頂点（特に町1から到達不能）があれば即 -1 にできます。

• 道路入力で同じ2町間の道路は高々1本ですが、念のため min を取る形にしておくと安全です。

• DPの初期値は十分大きい INF にし、到達していない状態はスキップします。

• 町番号はコード内で 0-index（町1→0）に直して扱うとビット演算と相性が良いです。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        N = next(it)
    except StopIteration:
        return
    M = next(it)

    INF = 10**18
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    # Floyd-Warshall for all-pairs shortest paths
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            nd_base = dik
            for j in range(N):
                nd = nd_base + dk[j]
                if nd < di[j]:
                    di[j] = nd

    # Must be able to reach every town from town 1
    for v in range(N):
        if dist[0][v] == INF:
            print(-1)
            return

    full = (1 << N) - 1
    dp = [[INF] * N for _ in range(1 << N)]
    dp[1][0] = 0

    for mask in range(1 << N):
        row = dp[mask]
        for i in range(N):
            cur = row[i]
            if cur == INF:
                continue
            di = dist[i]
            nmask_base = mask
            for j in range(N):
                if nmask_base & (1 << j):
                    continue
                nd = cur + di[j]
                nmask = nmask_base | (1 << j)
                if nd < dp[nmask][j]:
                    dp[nmask][j] = nd

    ans = INF
    for i in range(N):
        cost = dp[full][i] + dist[i][0]
        if cost < ans:
            ans = cost

    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。