概要

地点 \(1\) から出発して \(K\) 個の指定された届け先をすべて訪問し、地点 \(N\) に到着するまでの最短移動時間を求める問題です。

考察

\(K\) 個の届け先を訪れる順番は自由なので、すべての順番を試すと \(K!\) 通りあります。制約の \(K \leq 15\) では \(15! \approx 1.3 \times 10^{12}\) となり、すべてを試すとTLE（時間切れ）になります。

しかし、状態として「すでに訪問した届け先の集合」と「最後に訪問した届け先」を持つことで、計算量を大幅に削減できます。これは巡回セールスマン問題（TSP）の典型アプローチであり、ビットDPを用いると \(O(K^2 2^K)\) で解くことができます。

また、グラフ上の任意のノード間を移動する際の最短時間は、ダイクストラ法を用いて事前に計算しておくことで、DPの遷移を高速に行うことができます。

アルゴリズム

1. ターゲット間の最短距離の計算: 出発地点（地点 \(1\)）、到着地点（地点 \(N\)）、届け先（\(C_1, \dots, C_K\)）の合計 \(K+2\) 個のノードをターゲットとしてまとめます。それぞれのターゲットを始点としてダイクストラ法を実行し、すべてのターゲット間の最短距離を求めます。

2. ビットDPによる巡回経路の探索:

   • dp[mask][i]：訪問した届け先の集合が mask（ビット列）であり、最後に訪問した届け先が i 番目であるときの最小移動時間とします。
   • 初期状態として、出発地点から各届け先へ直接移動した場合の距離を設定します。
   • 各状態から、まだ訪問していない届け先 j へ移動する遷移を行い、dp テーブルを更新します。
   • 最終的に、すべての届け先を訪問した状態から、到着地点（地点 \(N\)）へ移動したときの最小移動時間が答えとなります。

計算量

• 時間計算量: \(O((K+2) M \log N + K^2 2^K)\) ダイクストラ法が \(K+2\) 回実行されるため \(O((K+2) M \log N)\)、ビットDPの遷移が \(O(K^2 2^K)\) です。制約下では十分に高速です。
• 空間計算量: \(O(N + M + K^2)\) グラフの隣接リストやダイクストラ法の配列で \(O(N + M)\)、ターゲット間の距離やDPテーブルで \(O(K^2)\) 程度のメモリを消費します。

実装のポイント

• 届け先のインデックスを管理しやすくするため、ターゲットのリストを [1, N] + C のように構成すると、出発地を 0、到着地を 1、各届け先を 2 以降のインデックスで扱えて便利です。

• DPの初期化では、dp[1 << i][i] = dist[0][i + 2] のように出発地（インデックス 0）から各届け先（インデックス i+2）への距離を設定します。

• DPの遷移後、すべての届け先を訪問した状態（full_mask = (1 << K) - 1）から到着地（インデックス 1）への距離 dist[i + 2][1] を足して最小値を求めます。

  ソースコード

import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    C = list(map(int, input().split()))
    # 始点(1), 終点(N), 届け先(C)
    targets = [1, N] + C
    T = len(targets)
    
    # 各targetからの最短距離を計算するためのDijkstra
    dist = [[0] * T for _ in range(T)]
    
    for start_idx in range(T):
        start_node = targets[start_idx]
        d = [10**18] * (N + 1)
        d[start_node] = 0
        pq = [(0, start_node)]
        while pq:
            cd, cn = heapq.heappop(pq)
            if cd > d[cn]:
                continue
            for nxt, w in adj[cn]:
                nd = cd + w
                if nd < d[nxt]:
                    d[nxt] = nd
                    heapq.heappush(pq, (nd, nxt))
        for end_idx in range(T):
            dist[start_idx][end_idx] = d[targets[end_idx]]
            
    # TSP DP
    # 始点: targets[0] (1)
    # 終点: targets[1] (N)
    # 届け先: targets[2] ~ targets[K+1] (C_1 ~ C_K)
    
    INF = 10**18
    dp = [[INF] * K for _ in range(1 << K)]
    
    # 初期化: 始点から各届け先への移動
    for i in range(K):
        dp[1 << i][i] = dist[0][i + 2]
        
    # DP遷移
    for mask in range(1, 1 << K):
        for i in range(K):
            if not (mask & (1 << i)):
                continue
            cur = dp[mask][i]
            if cur == INF:
                continue
            for j in range(K):
                if mask & (1 << j):
                    continue
                nxt_mask = mask | (1 << j)
                cost = cur + dist[i + 2][j + 2]
                if cost < dp[nxt_mask][j]:
                    dp[nxt_mask][j] = cost
                    
    # 最終状態から終点(N)への移動
    ans = INF
    full_mask = (1 << K) - 1
    for i in range(K):
        if dp[full_mask][i] != INF:
            cost = dp[full_mask][i] + dist[i + 2][1]
            if cost < ans:
                ans = cost
                
    print(ans)

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。