概要

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

\(K \leq 15\) と小さいため、「重要な地点間の最短距離」を求めたあと、bit DP で届け先を訪れる順番を最適化します。

考察

届け先を訪れる順番は自由です。
例えば届け先が \(C_1, C_2, C_3\) のとき、

\[ 1 \to C_2 \to C_1 \to C_3 \to N \]

のような順番で回ることができます。

このとき、各区間では必ず最短経路を使うのが最適です。
つまり、上の順番の移動時間は

\[ \operatorname{dist}(1, C_2) + \operatorname{dist}(C_2, C_1) + \operatorname{dist}(C_1, C_3) + \operatorname{dist}(C_3, N) \]

で考えればよいです。

したがって、まず必要なのは以下のような「重要な地点」同士の最短距離です。

• 出発地点 \(1\)
• 届け先 \(C_1, C_2, \dots, C_K\)
• 終点 \(N\)

重要な地点は全部で \(K+2\) 個しかありません。

ただし、全頂点間最短距離を Floyd-Warshall 法で求めると \(O(N^3)\) となり、\(N \leq 10^5\) なので不可能です。

一方で、辺の重みはすべて正なので、Dijkstra 法を使えます。
重要な地点からだけ Dijkstra 法を行えば、必要な距離だけを効率よく求められます。

その後、届け先を訪れる順番を bit DP で決めます。

素朴にすべての順列を試すと \(K!\) 通りです。
\(K=15\) のとき \(15!\) は非常に大きく、間に合いません。

そこで、集合を bit で管理する DP を使うことで、計算量を \(O(2^K K^2)\) に抑えます。

アルゴリズム

重要な地点を次のように並べます。

\[ P_0 = 1 \]

\[ P_i = C_i \quad (1 \leq i \leq K) \]

\[ P_{K+1} = N \]

1. 重要な地点間の最短距離を求める

各重要地点 \(P_0, P_1, \dots, P_K\) から Dijkstra 法を行います。

終点 \(N = P_{K+1}\) からは Dijkstra 法を行っていません。
なぜなら道路は双方向なので、

\[ \operatorname{dist}(C_i, N) \]

は、\(C_i\) から Dijkstra 法をした結果で分かるからです。

コードでは、pair_dist[a][b] を

\[ P_a \text{ から } P_b \text{ への最短距離} \]

として保持しています。

2. bit DP で届け先を訪れる順番を決める

DP を次のように定義します。

\[ dp[mask][i] \]

を、

• すでに訪れた届け先の集合が mask
• 最後にいる届け先が \(C_i\)

であるときの、地点 \(1\) からの最小移動時間とします。

ここで、mask は \(K\) ビットの整数です。
例えば \(K=4\) のとき、mask = 0101 なら \(C_0\) と \(C_2\) を訪問済み、という意味です。

初期化

最初に地点 \(1\) から直接 \(C_i\) に行く場合です。

\[ dp[1 << i][i] = \operatorname{dist}(1, C_i) \]

コードでは、

dp[1 << i][i] = pair_dist[0][i + 1]

です。

遷移

現在 \(C_i\) にいて、次にまだ訪れていない \(C_j\) に行くとします。

\[ dp[mask \cup \{j\}][j] = \min( dp[mask \cup \{j\}][j], dp[mask][i] + \operatorname{dist}(C_i, C_j) ) \]

コードでは、

nd = cur + d_from_i[j + 1]

として、次の届け先へ移動しています。

答え

すべての届け先を訪問済みの状態を full とします。

最後にいる届け先が \(C_i\) のとき、そこから地点 \(N\) に行けばよいので、

\[ dp[full][i] + \operatorname{dist}(C_i, N) \]

の最小値が答えです。

コードでは、

ans = INF
for i in range(K):
    val = dp[full][i] + pair_dist[i + 1][K + 1]
    ans = min(ans, val)

としています。

計算量

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

Dijkstra 法を \(K+1\) 回行います。
また、bit DP の状態数は \(2^K K\) 個で、それぞれから次の届け先への遷移を考えるため \(O(2^K K^2)\) です。

\(K \leq 15\) なので、bit DP は十分高速に実行できます。

実装のポイント

Dijkstra 法では、すべての頂点への距離を求める必要はありますが、欲しいのは重要な地点への距離だけです。

コードでは important_idx を用意し、現在取り出した頂点が重要地点かどうかを \(O(1)\) で判定しています。

important_idx = [-1] * (N + 1)
for i, v in enumerate(important):
    important_idx[v] = i

また、Dijkstra 法では優先度付きキューから取り出した時点で、その頂点への最短距離が確定します。
そのため、すべての重要地点への距離が確定したら、探索を途中で打ち切っています。

while hq and remain:

ただし、最悪計算量は通常の Dijkstra 法と同じです。

距離は最大でかなり大きくなる可能性があるため、INF = 10**30 のように十分大きい値を使っています。

ソースコード

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline

    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N + 1)]

    for _ in range(M):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))

    C = list(map(int, input().split()))

    important = [1] + C + [N]
    L = K + 2

    important_idx = [-1] * (N + 1)
    for i, v in enumerate(important):
        important_idx[v] = i

    INF = 10**30

    def dijkstra(start):
        dist = [INF] * (N + 1)
        dist[start] = 0

        res = [INF] * L
        remain = L

        hq = [(0, start)]
        heappush = heapq.heappush
        heappop = heapq.heappop
        g = graph
        idx = important_idx

        while hq and remain:
            d, v = heappop(hq)
            if d != dist[v]:
                continue

            ii = idx[v]
            if ii != -1 and res[ii] == INF:
                res[ii] = d
                remain -= 1

            for to, w in g[v]:
                nd = d + w
                if nd < dist[to]:
                    dist[to] = nd
                    heappush(hq, (nd, to))

        return res

    pair_dist = [dijkstra(v) for v in important[:-1]]

    size = 1 << K
    full = size - 1

    dp = [[INF] * K for _ in range(size)]

    for i in range(K):
        dp[1 << i][i] = pair_dist[0][i + 1]

    for mask in range(size):
        row = dp[mask]
        rest = full ^ mask

        for i in range(K):
            cur = row[i]
            if cur == INF:
                continue

            d_from_i = pair_dist[i + 1]
            b = rest

            while b:
                lsb = b & -b
                j = lsb.bit_length() - 1
                nm = mask | lsb
                nd = cur + d_from_i[j + 1]

                if nd < dp[nm][j]:
                    dp[nm][j] = nd

                b -= lsb

    ans = INF
    for i in range(K):
        val = dp[full][i] + pair_dist[i + 1][K + 1]
        if val < ans:
            ans = val

    print(ans)

if __name__ == "__main__":
    main()

---

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