概要

本問題は、地点1から出発し、指定された \(K\) 個の届け先をすべて訪問した上で、最終的に地点 \(N\) に到着するまでの最短移動時間を求める問題です。これは「巡回セールスマン問題（TSP）」の変形であり、制約 \(K \le 15\) に着目して、ダイクストラ法とビットDP（Bit DP）を組み合わせることで効率的に解くことができます。

考察

1. 素朴なアプローチとその限界

もし \(K\) が非常に大きければこの問題はNP困難であり、高速に解くことは困難です。 届け先を訪問する順番は \(K!\) 通りあります。\(K = 15\) のとき \(15! \approx 1.3 \times 10^{12}\) となり、すべての順列を愚直に探索すると実行時間制限に間に合いません（TLE）。

2. \(K\) の小ささに着目した解決策

私たちが最適化したいのは、「地点1」「\(K\) 個の届け先 \(C_1, \dots, C_K\)」「地点 \(N\)」という特定の地点間を移動する順番だけです。 したがって、問題を以下の2つのステップに分割して解くことができます。

1. 必要な地点間の最短距離をあらかじめ求める 地点数は \(N \le 10^5\) と大きいため、全点対間最短経路を求めるワーシャル・フロイド法（\(O(N^3)\)）は使えません。しかし、始点を1つに固定した最短経路であれば、ダイクストラ法を用いて \(O((N + M) \log N)\) で高速に求められます。 必要な始点は「地点1」と「\(K\) 個の届け先」の計 \(K+1\) 個だけなので、ダイクストラ法を \(K+1\) 回実行すれば、必要な地点間の最短距離をすべて求めることができます。

2. ビットDP（動的計画法）で巡回ルートを最適化する 「これまでに訪れた届け先の集合」と「現在いる届け先」を状態として持つ動的計画法（ビットDP）を適用します。 集合をビット（2進数）で表すことで、状態数を \(2^K \times K\) に抑えることができます。\(K = 15\) のとき、状態数は \(32768 \times 15 \approx 4.9 \times 10^5\) となり、十分に高速に処理できます。

---

アルゴリズム

ステップ1: ダイクストラ法による最短距離の計算

「地点1」および「\(K\) 個の届け先 \(C_1, \dots, C_K\)」の計 \(K+1\) 個の各地点を始点として、ダイクストラ法を実行します。 これにより、以下の地点間の最短距離を格納したテーブル dist を作成します。 - dist[0][j]: 地点1から各ターゲット（届け先、および地点 \(N\)）への最短距離 - dist[i][j] (\(1 \le i \le K\)): 届け先 \(C_i\) から各ターゲットへの最短距離

ステップ2: ビットDPによる巡回ルートの最適化

以下のDPテーブルを定義します。 - dp[mask][i]: これまでに訪れた届け先の集合が mask（ビット表現）であり、現在届け先 \(C_i\) にいるときの、移動時間の最小値。

1. 初期化: すべての dp の値を \(\infty\)（十分大きな値）で初期化します。 最初に地点1から最初の届け先 \(C_i\) に移動するため、以下のように初期化します。 $\(dp[2^i][i] = \text{dist}[0][i+1] \quad (0 \le i < K)\)\( *(※ `dist` のインデックス調整に注意：`dist` において地点1は `0`、届け先 \)C_i$ は i+1 に対応します)*

2. 遷移: 現在の状態 mask と現在地 \(i\) から、まだ訪れていない届け先 \(j\) （mask の \(j\) 番目のビットが0）へ移動する遷移を考えます。 $\(dp[\text{mask} \cup \{j\}][j] = \min(dp[\text{mask} \cup \{j\}][j], dp[\text{mask}][i] + \text{dist}[i+1][j+1])\)$

3. ゴール（地点 \(N\) への移動）: すべての届け先を訪れた状態（mask が \(2^K - 1\)）から、最後に地点 \(N\) へ移動します。 求める答えは、以下の値の最小値です。 $\(\min_{0 \le i < K} (dp[2^K - 1][i] + \text{dist}[i+1][K+1])\)\( *(※ `dist` において地点 \)N$ は K+1 に対応します)*

---

計算量

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

  • ダイクストラ法部分: \(K+1\) 回実行するため、 \(O(K (M + N \log N))\) です。
  • ビットDP部分: 状態数が \(2^K \times K\)、各状態からの遷移数が \(K\) であるため、 \(O(2^K \cdot K^2)\) です。
  • \(N = 10^5, M = 5 \times 10^4, K = 15\) のとき、全体の演算回数は \(3 \times 10^7\) 回程度に収まり、実行時間制限内に余裕で間に合います。

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

  • 隣接リストの保持に \(O(N + M)\)、DPテーブルに \(O(2^K \cdot K)\) のメモリを使用します。こちらもメモリ制限に十分収まります。

---

実装のポイント

• インデックスの対応関係: プログラム内での地点番号は 0-indexed に変換しておくとバグを減らせます。 本コードでは、ダイクストラ法で用いる始点リスト sources と終点リスト targets を以下のように整理し、インデックスの対応を明確にしています。

  • sources = [0] + C (長さ \(K+1\))
  • targets = [0] + C + [N - 1] (長さ \(K+2\))

• ビット演算: 集合の表し方として、 \(i\) 番目の届け先を訪れたことを 1 << i 番目のビットが立っていることで表現します。

  • まだ訪れていない判定: not (mask & (1 << j))

  • 新しく訪問した状態への遷移: mask | (1 << j) これらを用いて簡潔かつ高速に状態遷移を記述できます。

    ソースコード

import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    adj = [[] for _ in range(N)]
    idx = 3
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        w = int(input_data[idx+2])
        adj[u].append((v, w))
        adj[v].append((u, w))
        idx += 3
        
    C = []
    for _ in range(K):
        C.append(int(input_data[idx]) - 1)
        idx += 1
        
    sources = [0] + C
    targets = [0] + C + [N - 1]
    
    INF = 10**18
    dist = [[INF] * (K + 2) for _ in range(K + 1)]
    
    for i, s in enumerate(sources):
        d = [INF] * N
        d[s] = 0
        pq = [(0, s)]
        while pq:
            dist_u, u = heapq.heappop(pq)
            if dist_u > d[u]:
                continue
            for v, w in adj[u]:
                if d[v] > dist_u + w:
                    d[v] = dist_u + w
                    heapq.heappush(pq, (d[v], v))
        for j, t in enumerate(targets):
            dist[i][j] = d[t]
            
    dp = [[INF] * K for _ in range(1 << K)]
    
    for i in range(K):
        dp[1 << i][i] = dist[0][i+1]
        
    for mask in range(1, 1 << K):
        dp_mask = dp[mask]
        for i in range(K):
            d_curr = dp_mask[i]
            if d_curr == INF:
                continue
            dist_i = dist[i+1]
            for j in range(K):
                if not (mask & (1 << j)):
                    next_mask = mask | (1 << j)
                    new_d = d_curr + dist_i[j+1]
                    if dp[next_mask][j] > new_d:
                        dp[next_mask][j] = new_d
                        
    ans = INF
    full_mask = (1 << K) - 1
    dp_full = dp[full_mask]
    for i in range(K):
        val = dp_full[i] + dist[i+1][K+1]
        if val < ans:
            ans = val
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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