概要

地点 \(1\) から出発し、指定された \(K\) 個の届け先をすべて訪問してから地点 \(N\) に到着するまでの最小移動時間を求める問題です。届け先を訪れる順番は自由に選べます。これは「巡回セールスマン問題（TSP）」を最短経路と組み合わせた典型問題です。

考察

重要な観察 1: 順番の最適化が必要

届け先を訪れる順番は自由なので、\(K\) 個の届け先をどの順番で回るかをすべて試す必要があります。素朴に全順列を試すと \(O(K!)\) 通りあり、\(K = 15\) では \(15! \approx 1.3 \times 10^{12}\) となり、到底間に合いません。

そこで、bitDP（ビットマスクを使った動的計画法） を使い、\(O(2^K \cdot K^2)\) で順番の最適化を行います。

重要な観察 2: 地点間の最短距離だけが重要

途中で届け先以外の地点を自由に通過でき、同じ地点・道路を何度通ってもよいので、

• 「地点 \(1\) → ある届け先」
• 「ある届け先 → 別の届け先」
• 「ある届け先 → 地点 \(N\)」

の各移動コストは、グラフ上の最短経路（最短距離） に置き換えてよいことがわかります。つまり、元のグラフを「重要な地点（地点 \(1\)、各届け先、地点 \(N\)）だけからなる完全グラフ」に圧縮し、その上でTSPを解けばよいのです。

距離の計算方法

必要な最短距離は次の通りです。

• 地点 \(1\) から各届け先 \(C_i\) までの距離
• 各届け先 \(C_i\) から別の届け先 \(C_j\) までの距離
• 各届け先 \(C_i\) から地点 \(N\) までの距離

これらは、各届け先 \(C_i\) を始点としたダイクストラ法を \(K\) 回、加えて地点 \(1\) を始点としたダイクストラ法を \(1\) 回行うことですべて求められます（道路は双方向なので \(C_i\) から \(N\) への距離は \(C_i\) 始点のダイクストラで得られます）。

合計 \(K + 1\) 回のダイクストラ法を実行します。

アルゴリズム

ステップ1: 最短距離の前計算

• 地点 \(1\) を始点にダイクストラ → start_to[i]（地点 \(1\) から \(C_i\) への距離）
• 各 \(C_i\) を始点にダイクストラ →
  • dd[i][j]（\(C_i\) から \(C_j\) への距離）
  • to_N[i]（\(C_i\) から地点 \(N\) への距離）

ステップ2: bitDP

dp[mask][i] を「これまでに mask で表される届け先集合をすべて訪問済みで、最後に訪れた届け先が \(i\) であるときの、地点 \(1\) からの最小移動時間」と定義します。

初期化: 最初に訪れる届け先が \(i\) の場合、 $\(dp[\{i\}][i] = \text{start\_to}[i]\)$

遷移: 状態 \((mask, i)\) から、まだ訪れていない届け先 \(j\) へ移動する場合、 $\(dp[mask \cup \{j\}][j] \leftarrow \min\big(dp[mask \cup \{j\}][j],\ dp[mask][i] + dd[i][j]\big)\)$

答え: すべての届け先を訪問した状態 full（\(=2^K - 1\)）から、最後の届け先 \(i\) を経て地点 \(N\) へ向かう最小値を取ります。 $\(\text{ans} = \min_i \big(dp[full][i] + \text{to\_N}[i]\big)\)$

計算量

• ダイクストラ法を \(K + 1\) 回実行: \(O\big((K+1)(M + N)\log N\big)\)
• bitDP: \(O(2^K \cdot K^2)\)

これらを合わせて、

• 時間計算量: \(O\big(K (M + N) \log N + 2^K K^2\big)\)
• 空間計算量: \(O\big(K N + 2^K K\big)\)

\(K \le 15\) なので \(2^K K^2 \approx 7.4 \times 10^6\)、ダイクストラ部分も十分高速で、制約内に収まります。

実装のポイント

• 距離は非常に大きくなる: \(W_i\) は最大 \(10^9\)、経路は複数の届け先をまたぐため、距離の合計は \(64\) ビット整数の範囲が必要です。Pythonでは多倍長整数なのでオーバーフローの心配はありませんが、C++などでは long long を使う必要があります。

• 無効な状態のスキップ: bitDPの遷移では、dp[mask][i] が INF（到達不能）の場合や、\(i\) が mask に含まれない場合をスキップすることで無駄な計算を省きます。

• 入力の高速読み込み: \(N, M\) が大きいので、sys.stdin.buffer.read() でまとめて読み込むと高速です。

• ダイクストラはヒープ（優先度付きキュー）で実装: heapq を用い、取り出した距離が記録済みの距離より大きい場合（古い情報）はスキップする定石を使っています。

  ソースコード

import sys
import heapq

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))

    C = [int(data[idx + i]) for i in range(K)]
    idx += K

    INF = float('inf')

    def dijkstra(start):
        dist = [INF] * (N + 1)
        dist[start] = 0
        h = [(0, start)]
        while h:
            d, u = heapq.heappop(h)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(h, (nd, v))
        return dist

    # distances from start node 1
    d_start = dijkstra(1)
    start_to = [d_start[C[i]] for i in range(K)]

    # distances from each delivery
    dd = [None] * K
    to_N = [0] * K
    delivery_dist = []
    for i in range(K):
        di = dijkstra(C[i])
        delivery_dist.append(di)
        to_N[i] = di[N]

    dd = [[delivery_dist[i][C[j]] for j in range(K)] for i in range(K)]

    full = (1 << K) - 1
    dp = [[INF] * K for _ in range(1 << K)]
    for i in range(K):
        dp[1 << i][i] = start_to[i]

    for mask in range(1 << K):
        row = dp[mask]
        for i in range(K):
            if not (mask >> i) & 1:
                continue
            cur = row[i]
            if cur == INF:
                continue
            ddi = dd[i]
            for j in range(K):
                if (mask >> j) & 1:
                    continue
                nd = cur + ddi[j]
                nm = mask | (1 << j)
                if nd < dp[nm][j]:
                    dp[nm][j] = nd

    ans = INF
    for i in range(K):
        v = dp[full][i] + to_N[i]
        if v < ans:
            ans = v

    print(ans)

main()

---

この解説は claude4.8opus-high によって生成されました。