概要

本問題は、重み付き有向グラフ上で都市1から出発し、制限時間 \(T\) 以内にいくつかの都市を訪問して、達成できたミッションの報酬の合計を最大化する問題です。

ミッションに関係する都市の総数が高々14個と非常に小さいことに着目し、ダイクストラ法、ビットDP（巡回セールスマン問題の応用）、および高速ゼータ変換（SOS DP）を組み合わせることで、制限時間内に効率よく最適解を求めることができます。

---

考察

1. 重要な都市の絞り込み

都市の総数 \(N\) は最大で \(10^4\) と大きいですが、ミッションの条件に関係する都市の総数は高々14個（\(\bigcup S_j \le 14\)）しかありません。 スタート地点である都市1と、ミッションに登場する都市を合わせた集合を「重要都市 \(V_{\text{imp}}\)」と定義します。この重要都市の数 \(D = |V_{\text{imp}}|\) は最大でも \(15\) です。

ミッションを達成するためには、重要都市を巡る必要があります。重要都市以外の都市は、単に重要都市間を移動するための「経由地」としてしか機能しません。したがって、重要都市間の最短移動時間さえ分かれば、元の大きなグラフを直接探索する必要はなくなります。

2. 重要都市間の最短距離の計算

各重要都市 \(u \in V_{\text{imp}}\) を始点として、ダイクストラ法を適用します。 重要都市の数 \(D \le 15\) なので、ダイクストラ法を \(D\) 回実行すれば、すべての重要都市ペア間の最短距離を求めることができます。

3. ビットDPによる訪問パターンの探索

訪問した重要都市の集合をビット（mask）で管理します。 これは「巡回セールスマン問題（TSP）」に非常によく似た設定であり、以下のビットDP（Bit DP）で解くことができます。

• \(dp[mask][i]\) := これまでに訪問した重要都市の集合が \(mask\) であり、現在重要都市 \(i\) にいるときの、移動時間の最小値

初期状態は、都市1（インデックス0とします）のみを訪問して都市1にいる状態なので、\(dp[1][0] = 0\)、それ以外は \(\infty\) とします。 このDPの遷移は、次に訪れる重要都市 \(j\) を全探索することで、 \(O(2^D \cdot D^2)\) で行えます。\(D \le 15\) であるため、状態数は \(2^{15} \times 15 \approx 5 \times 10^5\) となり、十分高速に動作します。

DP終了後、各 \(mask\) について \(\min_{i} dp[mask][i] \le T\) を満たすものが「制限時間 \(T\) 以内に訪問可能な都市の集合」となります。

4. 報酬の集計の高速化

ある訪問済みの重要都市の集合 \(mask\) が決まったとき、獲得できる報酬の総和を求めたいです。 ミッション \(j\) の都市集合 \(S_j\) をビットで表したものを \(mask_j\) とします。 獲得できる報酬は、「\(mask_j\) が \(mask\) の部分集合である（\(mask \ \& \ mask_j = mask_j\)）」を満たすすべてのミッション \(j\) の報酬 \(P_j\) の総和です。

これをすべての \(mask\) について愚直に計算すると \(O(2^D \cdot K)\) かかり、これでも間に合いますが、高速ゼータ変換（SOS DP）を用いることで \(O(2^D \cdot D)\) でより高速かつスマートに計算できます。

---

アルゴリズム

1. 重要都市の抽出: すべてのミッションに登場する都市と、スタート地点である都市1を回収し、重複を排除して重要都市のリスト \(V_{\text{imp}}\) を作成します。重要都市の数を \(D\) とします。

2. 重要都市間の最短距離計算: 各重要都市 \(v \in V_{\text{imp}}\) からダイクストラ法を実行し、重要都市間の距離行列 dist_matrix（サイズ \(D \times D\)）を構築します。

3. 巡回DP（ビットDP）: 都市1から出発し、重要都市を訪ねる最短時間をビットDPで求めます。 \(dp[mask][i]\) の更新が終わったら、各 \(mask\) について、いずれかの都市 \(i\) での最小時間が \(T\) 以下であるか判定し、到達可能な \(mask\) を記録します。

4. 高速ゼータ変換による報酬の累積:

   • 配列 val（サイズ \(2^D\)）を用意し、各ミッション \(j\) について、その必要都市集合のビット表現 \(mask_j\) の位置に報酬 \(P_j\) を加算します。
   • 高速ゼータ変換を行い、各 \(mask\) に対して「\(mask\) の部分集合であるようなすべての \(mask_j\) の報酬の総和」を計算します。

5. 最大値の取得: 到達可能なすべての \(mask\) のうち、val[mask] の最大値を出力します。

---

計算量

時間計算量

• ダイクストラ法: 重要都市の数 \(D\) 回だけ実行するため、 \(O(D(N + M \log N))\)。
• ビットDP: 状態数 \(2^D \cdot D\) に対し、次の遷移先が \(D\) 通りあるため、 \(O(2^D \cdot D^2)\)。
• 高速ゼータ変換: \(O(2^D \cdot D)\)。

全体の時間計算量は、 \(O(D(N + M \log N) + 2^D \cdot D^2)\) となります。 \(N, M \le 10^4, D \le 15\) であるため、実行時間は最悪ケースでも 0.1 秒未満に収まり、非常に高速です。

空間計算量

• グラフの隣接リスト: \(O(N + M)\)。
• 最短距離行列: \(O(D^2)\)。
• DPテーブルおよび累積和配列: \(O(2^D \cdot D)\)。

全体の空間計算量は、 \(O(N + M + 2^D \cdot D)\) となり、メモリ制限に対しても十分に余裕があります。

---

実装のポイント

高速ゼータ変換（SOS DP）の仕組み

コード内の以下の部分は、下位集合の累積和を求める高速ゼータ変換です。

for i in range(D):
    bit = 1 << i
    for mask in range(num_states):
        if mask & bit:
            val[mask] += val[mask ^ bit]

この処理を行うことで、val[mask] には「mask の部分集合（＝その都市集合だけで達成できるミッション）の報酬の総和」が正しく足し込まれます。 これにより、各 \(mask\) に対して \(O(1)\) でその時点で得られる最大報酬を参照できるようになります。

ソースコード

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])
    T = int(input_data[3])

    idx = 4
    edges = []
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx + 1])
        w = int(input_data[idx + 2])
        edges.append((u, v, w))
        idx += 3

    missions = []
    for _ in range(K):
        sz = int(input_data[idx])
        S_j = []
        for _ in range(sz):
            S_j.append(int(input_data[idx + 1]))
            idx += 1
        idx += 1
        P_j = int(input_data[idx])
        idx += 1
        missions.append((S_j, P_j))

    U_all = set()
    for S_j, P_j in missions:
        for s in S_j:
            U_all.add(s)

    V_imp = [1]
    for u in U_all:
        if u != 1:
            V_imp.append(u)

    D = len(V_imp)
    node_to_idx = {v: i for i, v in enumerate(V_imp)}

    adj = [[] for _ in range(N + 1)]
    for u, v, w in edges:
        adj[u].append((v, w))

    INF = 10**15

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

    dist_matrix = [[INF] * D for _ in range(D)]
    for i in range(D):
        d = dijkstra(V_imp[i])
        for j in range(D):
            dist_matrix[i][j] = d[V_imp[j]]

    num_states = 1 << D
    dp = [INF] * (num_states * D)
    dp[1 * D + 0] = 0

    for mask in range(1, num_states, 2):
        base = mask * D
        for i in range(D):
            val = dp[base + i]
            if val == INF:
                continue
            dist_i = dist_matrix[i]
            for j in range(D):
                if not (mask & (1 << j)):
                    next_mask = mask | (1 << j)
                    n_idx = next_mask * D + j
                    new_val = val + dist_i[j]
                    if new_val < dp[n_idx]:
                        dp[n_idx] = new_val

    possible = [False] * num_states
    for mask in range(1, num_states, 2):
        min_t = INF
        base = mask * D
        for i in range(D):
            if dp[base + i] < min_t:
                min_t = dp[base + i]
        if min_t <= T:
            possible[mask] = True

    val = [0] * num_states
    for S_j, P_j in missions:
        mask_j = 0
        for s in S_j:
            mask_j |= 1 << node_to_idx[s]
        val[mask_j] += P_j

    for i in range(D):
        bit = 1 << i
        for mask in range(num_states):
            if mask & bit:
                val[mask] += val[mask ^ bit]

    ans = 0
    for mask in range(1, num_states, 2):
        if possible[mask]:
            if val[mask] > ans:
                ans = val[mask]
    print(ans)


if __name__ == "__main__":
    solve()

---

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