概要

この問題は、町1から出発して全ての町を少なくとも1回ずつ訪問し、再び町1に戻ってくるための最短時間を求める問題です。いわゆる「巡回セールスマン問題（TSP）」の変種ですが、同じ町や道路を何度も通ってよいという点が特徴です。

考察

1. 「少なくとも1回」を「ちょうど1回」に変換する

通常の巡回セールスマン問題は「各都市をちょうど1回ずつ通る」という制約がありますが、この問題では同じ町を複数回通ることが許されています。しかし、あらかじめ全町ペア間の最短距離を求めておけば、「町 A から町 B へ最短経路で移動する」という操作を「1回の移動」とみなすことで、通常の巡回セールスマン問題として扱うことができます。

例えば、町1から町3へ行く途中で町2を通ったとしても、それは「町1→町2→町3」という移動を1つにまとめたものと考えれば、実質的に全ての町を「最短で巡る」問題に集約されます。

2. 制約に注目

町の数 \(N\) が最大で \(15\) と非常に小さいことに注目します。 全順列を試すと \(15! \approx 1.3 \times 10^{12}\) となり間に合いませんが、ビットDP（動的計画法）を用いることで \(O(N^2 2^N)\) の計算量で解くことができます。\(15^2 \times 2^{15} \approx 7.3 \times 10^6\) であり、制限時間内に十分収まります。

アルゴリズム

ステップ1：全点対間最短経路の計算（ワーシャル・フロイド法）

まず、与えられた道路情報から、任意の2つの町 \((i, j)\) 間の最短移動時間を求めます。 これはワーシャル・フロイド法を用いることで \(O(N^3)\) で計算可能です。もし、ある町から別の町へ行く経路が存在しない場合、その距離は無限大（INF）として扱います。

ステップ2：ビットDPによる巡回パスの計算

次に、以下のDPテーブルを定義します。 dp[mask][v] ： 現在までに訪れた町の集合が mask で、今いる町が v であるときの移動時間の最小値

• mask は、各町を訪問済みなら1、未訪問なら0とするビット表現（整数）です。
• 初期状態：dp[1][0] = 0（町1（インデックス0）にいて、訪問済みは町1のみ）
• 遷移：今いる町 u から次に訪れる町 v を選び、dp[mask | (1 << v)][v] を更新します。

ステップ3：町1への帰還と最終回答

全ての町を訪問した状態 dp[(1 << N) - 1][u]（全てのビットが1の状態）まで計算したら、最後に今いる町 u から出発地点の町1に戻る時間を加算します。 その中での最小値が答えとなります。どこかの町へ到達できない場合や、全ての町を巡って戻ってこれない場合は -1 を出力します。

計算量

• 時間計算量: \(O(N^3 + N^2 2^N)\)
  • ワーシャル・フロイド法に \(O(N^3)\)
  • ビットDPの遷移に \(O(N^2 2^N)\) かかります。
• 空間計算量: \(O(N^2 + N 2^N)\)
  • 最短距離行列に \(O(N^2)\)
  • DPテーブルに \(O(N 2^N)\) 使用します。

実装のポイント

• インデックスの調整: 問題文では町が \(1 \sim N\) ですが、コード上では \(0 \sim N-1\) として扱うとビット演算がしやすくなります。

• 無限大の初期化: 距離やDPテーブルの初期値は、十分に大きな値（10^15 など）で初期化してください。

• 到達可能性の判定: 全ての町を回る前に、そもそも町1から到達できない町がある場合は、即座に -1 を出力する処理を入れると効率的です。

  ソースコード

import sys

# The problem asks for the minimum travel time to visit all N towns at least once,
# starting from town 1 and returning to town 1.
# This is a variation of the Traveling Salesperson Problem (TSP). 
# Since we can visit towns and roads multiple times, we can simplify the problem 
# by first calculating the shortest paths between all pairs of towns.
# Then, we solve the standard TSP on the resulting complete graph.

def solve():
    # Read all input from standard input and split into a list of strings
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N is the number of towns, M is the number of roads
    N = int(input_data[0])
    M = int(input_data[1])
    
    # Use a large integer for infinity. The maximum possible travel time is 
    # well within this limit (max N * max W = 15 * 10^6).
    INF = 10**18
    
    # dist[i][j] will store the shortest path distance between town i and town j.
    # Initialize with INF, and 0 for the distance from a town to itself.
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0
        
    ptr = 2
    for _ in range(M):
        if ptr + 2 >= len(input_data):
            break
        u = int(input_data[ptr]) - 1
        v = int(input_data[ptr+1]) - 1
        w = int(input_data[ptr+2])
        # If multiple roads exist between the same two towns, keep only the shortest one.
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
        ptr += 3
        
    # Floyd-Warshall algorithm to compute all-pairs shortest paths.
    # This allows us to treat the problem as a standard TSP on a complete graph.
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            di = dist[i]
            dik = di[k]
            if dik >= INF:
                continue
            for j in range(N):
                new_dist = dik + dk[j]
                if new_dist < di[j]:
                    di[j] = new_dist
    
    # If any town is not reachable from town 1 (index 0), it is impossible to visit all towns.
    for i in range(N):
        if dist[0][i] >= INF:
            print("-1")
            return

    # DP for TSP:
    # dp[mask][u] = minimum distance to have visited the set of towns represented by 'mask',
    # with the current location being town 'u'.
    # 'mask' is a bitmask where the i-th bit is 1 if town i+1 has been visited.
    num_states = 1 << N
    dp = [[INF] * N for _ in range(num_states)]
    
    # Starting point: Town 1 (index 0), distance is 0.
    dp[1][0] = 0
    
    # Iterate through all bitmasks representing subsets of visited towns.
    for mask in range(1, num_states):
        dp_mask = dp[mask]
        
        # Optimization: Pre-calculate which towns are not yet in the current mask.
        not_in_mask = [v for v in range(N) if not (mask & (1 << v))]
        
        # For each town 'u' that could be the current location:
        for u in range(N):
            curr_dist = dp_mask[u]
            if curr_dist >= INF:
                continue
            
            # Try moving to each town 'v' that has not been visited yet.
            dist_u = dist[u]
            for v in not_in_mask:
                new_mask = mask | (1 << v)
                new_dist = curr_dist + dist_u[v]
                if dp[new_mask][v] > new_dist:
                    dp[new_mask][v] = new_dist
                        
    # The final answer is the minimum distance to visit all towns (full_mask)
    # and then return to the starting town (town 1, index 0).
    ans = INF
    full_mask = num_states - 1
    dp_full = dp[full_mask]
    dist_0 = dist[0]
    for u in range(N):
        if dp_full[u] < INF:
            # Add the shortest path distance from the last town u back to town 1.
            ans = min(ans, dp_full[u] + dist_0[u])
            
    # If ans is still INF, it means it was impossible to visit all towns and return.
    if ans >= INF:
        print("-1")
    else:
        print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。