概要

この問題は、制限時間 \(T\) 以内に都市 \(1\) から出発して複数の都市を巡り、達成できたミッション（指定された都市集合をすべて訪問する）の報酬の合計を最大化する問題です。ミッションに関係する都市の総数が最大 \(14\) と非常に少ないため、巡回セールスマン問題（TSP）のような動的計画法（Bit DP）を用いて解くことができます。

考察

1. 重要な制約への注目

最も重要な制約は、「すべてのミッションに登場する都市の種類数は高々 14」 という点です。 都市の総数 \(N\) は \(10^4\) と大きいですが、報酬に関係する特定の都市（以下、ターゲット都市と呼びます）だけを効率よく回る方法を考えればよいことになります。

2. 最短経路の利用

ターゲット都市から別のターゲット都市へ移動する際、わざわざ遠回りをする必要はありません。あらかじめダイクストラ法を用いて、各ターゲット都市間の最短距離を求めておくことで、グラフ全体を考える代わりにターゲット都市間のみの移動を考えることができます。

3. ミッション達成の条件

あるミッション \(j\) が達成できる条件は、「訪問済みの都市の集合」が「ミッション \(j\) の要求する都市集合 \(S_j\)」を包含していることです。 都市 \(1\) は最初から訪問済みであるため、ターゲット都市の集合に含めるか、あるいはミッションの条件から除外して考えることができます。

アルゴリズム

ステップ1：事前準備

1. ミッションに登場する全都市をリストアップし、重複を除いた集合 \(L\) を作成します（最大 14 都市）。
2. 都市 \(1\) および集合 \(L\) に含まれる各都市を始点としてダイクストラ法を実行し、以下の距離を求めます。
   • 都市 \(1\) から各ターゲット都市への最短距離
   • ターゲット都市間の相互の最短距離

ステップ2：Bit DP による最短移動時間の計算

ターゲット都市の集合をビットマスクで管理し、以下の DP を行います。 - dp[mask][i]：ターゲット都市の集合 mask を訪問済みで、最後に都市 i にいるときの最小合計時間

初期状態： - dp[1 << i][i] = (都市 1 から都市 i への距離) （ただし、その距離 \(\le T\) の場合）

遷移： - dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])

この DP 終了後、各 mask について「その集合の都市をすべて訪問するために必要な最小時間」を min_dist[mask] = min(dp[mask][i]) として求めます。

ステップ3：報酬の計算（高速ゼータ変換 / SOS DP）

各 mask に対して、その都市集合をちょうど訪問したときに得られる「直接的な報酬」を記録します。 しかし、実際に mask を訪問したときに得られる報酬は、mask の部分集合であるすべてのミッション報酬の総和です。

これを効率的に計算するために、高速ゼータ変換（Sum Over Subsets DP） を使用します。 - total_reward[mask] = \(\sum_{sub \subseteq mask} reward\_direct[sub]\)

ステップ4：最終回答

min_dist[mask] <= T を満たすすべての mask について、total_reward[mask] の最大値を求めます。

計算量

ターゲット都市の数を \(L\) (\(L \le 14\)) とします。

• 時間計算量: \(O(L(N + M) \log N + L^2 2^L)\)
  • ダイクストラ法: \(O(L(N + M) \log N)\)
  • Bit DP: \(O(L^2 2^L)\)
  • 高速ゼータ変換: \(O(L 2^L)\)
• 空間計算量: \(O(N + M + L 2^L)\)
  • グラフの隣接リスト、DP テーブルなど。

\(L=14\) のとき \(2^{14} = 16384\) なので、十分高速に動作します。

実装のポイント

• 都市 1 の扱い: 都市 1 は最初から訪問済みなので、ミッションの集合 \(S_j\) に含まれていても無視して構いません。ターゲット都市リストには都市 1 以外の都市を入れるとビット数を節約できます。

• 到達不能な経路: ダイクストラ法で到達できない場合は十分大きな値（INF）で初期化し、時間制限 \(T\) を超えないか常にチェックしてください。

• 報酬の集計: ミッションが同じ \(S_j\) を持つ可能性があるため、最初に reward_direct を計算する際は加算するようにします。

  ソースコード

import sys
import heapq

# The problem asks for the maximum total reward from missions that can be completed 
# within a time limit T, starting from city 1. A mission is satisfied if all 
# cities in its requirement set S_j are visited. The total number of unique cities 
# in the union of all S_j is at most 14. This suggests a Traveling Salesperson 
# Problem (TSP) style dynamic programming approach.

def solve():
    # Fast I/O to handle potentially large inputs
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Read N, M, K, T
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    T = int(input_data[3])
    
    # Build the adjacency list for the directed graph
    adj = [[] for _ in range(N + 1)]
    idx = 4
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        w = int(input_data[idx+2])
        adj[u].append((v, w))
        idx += 3
        
    # Read missions and identify all unique cities involved (excluding city 1)
    missions = []
    target_cities_set = set()
    for _ in range(K):
        s_len = int(input_data[idx])
        s_set = []
        for i in range(s_len):
            city = int(input_data[idx + 1 + i])
            s_set.append(city)
            if city != 1:
                target_cities_set.add(city)
        p = int(input_data[idx + 1 + s_len])
        missions.append((s_set, p))
        idx += s_len + 2
        
    # List of unique target cities other than city 1
    target_cities = sorted(list(target_cities_set))
    L = len(target_cities)
    city_to_idx = {city: i for i, city in enumerate(target_cities)}
    
    # Use a large value for infinity
    INF = 10**18
    
    # Dijkstra's algorithm to find shortest paths from a given start city
    def dijkstra(start_node):
        dists = [INF] * (N + 1)
        dists[start_node] = 0
        pq = [(0, start_node)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dists[u]:
                continue
            for v, w in adj[u]:
                new_d = d + w
                if new_d < dists[v]:
                    dists[v] = new_d
                    heapq.heappush(pq, (new_d, v))
        return dists

    # Pre-calculate shortest paths from city 1 and between all target cities
    dist_from_1 = []
    dists_1 = dijkstra(1)
    for city in target_cities:
        dist_from_1.append(dists_1[city])
        
    dist_matrix = [[INF] * L for _ in range(L)]
    for i in range(L):
        dists_i = dijkstra(target_cities[i])
        for j in range(L):
            dist_matrix[i][j] = dists_i[target_cities[j]]
            
    # TSP DP: dp[mask][i] is the minimum time to visit cities in mask and end at target_cities[i]
    dp = [[INF] * L for _ in range(1 << L)]
    for i in range(L):
        if dist_from_1[i] <= T:
            dp[1 << i][i] = dist_from_1[i]
            
    bits = [1 << i for i in range(L)]
    for mask in range(1, 1 << L):
        dp_mask = dp[mask]
        for i in range(L):
            d = dp_mask[i]
            if d > T:
                continue
            dist_matrix_i = dist_matrix[i]
            for j in range(L):
                if not (mask & bits[j]):
                    new_d = d + dist_matrix_i[j]
                    if new_d <= T:
                        new_mask = mask | bits[j]
                        if new_d < dp[new_mask][j]:
                            dp[new_mask][j] = new_d
                            
    # min_dist[mask] is the minimum time to visit all cities in mask
    min_dist = [INF] * (1 << L)
    min_dist[0] = 0
    for mask in range(1, 1 << L):
        d_min = min(dp[mask])
        min_dist[mask] = d_min
        
    # Calculate rewards for each exact set of visited target cities
    reward_direct = [0] * (1 << L)
    for s_set, p in missions:
        m_j = 0
        for s in s_set:
            if s != 1:
                m_j |= (1 << city_to_idx[s])
        reward_direct[m_j] += p
        
    # SOS (Sum Over Subsets) DP to find total rewards for any visited set
    for i in range(L):
        bit = bits[i]
        for mask in range(1 << L):
            if mask & bit:
                reward_direct[mask] += reward_direct[mask ^ bit]
                
    # Maximize rewards among reachable subsets of target cities
    ans = 0
    for mask in range(1 << L):
        if min_dist[mask] <= T:
            if reward_direct[mask] > ans:
                ans = reward_direct[mask]
    print(ans)

if __name__ == "__main__":
    solve()

---

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