Overview

This problem asks you to start from city \(1\), visit multiple cities within a time limit \(T\), and maximize the total reward from completed missions (where a mission requires visiting all cities in a specified set). Since the total number of cities involved in missions is at most \(14\), this can be solved using dynamic programming similar to the Traveling Salesman Problem (Bit DP).

Analysis

1. Focusing on the Key Constraint

The most important constraint is that “the total number of distinct cities appearing across all missions is at most 14”. Although the total number of cities \(N\) can be as large as \(10^4\), we only need to consider how to efficiently visit the specific cities related to rewards (hereafter called target cities).

2. Using Shortest Paths

When moving from one target city to another, there is no need to take detours. By precomputing the shortest distances between all pairs of target cities using Dijkstra’s algorithm, we can consider only movements between target cities instead of the entire graph.

3. Mission Completion Conditions

A mission \(j\) is completed when the “set of visited cities” is a superset of “the set of cities \(S_j\) required by mission \(j\)”. Since city \(1\) is already visited from the start, it can either be included in the set of target cities or excluded from mission conditions.

Algorithm

Step 1: Preprocessing

1. List all cities appearing in missions and create a deduplicated set \(L\) (at most 14 cities).
2. Run Dijkstra’s algorithm starting from city \(1\) and each city in set \(L\) to compute the following distances:
   • Shortest distance from city \(1\) to each target city
   • Shortest distances between all pairs of target cities

Step 2: Computing Minimum Travel Time with Bit DP

Manage the set of target cities using a bitmask and perform the following DP: - dp[mask][i]: The minimum total time when the set of target cities mask has been visited and you are currently at city i

Initial state: - dp[1 << i][i] = (distance from city 1 to city i) (only if that distance \(\le T\))

Transition: - dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])

After this DP is complete, for each mask, compute the “minimum time required to visit all cities in that set” as min_dist[mask] = min(dp[mask][i]).

Step 3: Computing Rewards (Fast Zeta Transform / SOS DP)

For each mask, record the “direct reward” obtained when exactly that set of cities is visited. However, the actual reward obtained when visiting mask is the sum of all mission rewards whose required sets are subsets of mask.

To compute this efficiently, we use the Fast Zeta Transform (Sum Over Subsets DP): - total_reward[mask] = \(\sum_{sub \subseteq mask} reward\_direct[sub]\)

Step 4: Final Answer

Find the maximum value of total_reward[mask] over all mask satisfying min_dist[mask] <= T.

Complexity

Let the number of target cities be \(L\) (\(L \le 14\)).

• Time Complexity: \(O(L(N + M) \log N + L^2 2^L)\)
  • Dijkstra’s algorithm: \(O(L(N + M) \log N)\)
  • Bit DP: \(O(L^2 2^L)\)
  • Fast Zeta Transform: \(O(L 2^L)\)
• Space Complexity: \(O(N + M + L 2^L)\)
  • Graph adjacency list, DP tables, etc.

When \(L=14\), \(2^{14} = 16384\), so the solution runs sufficiently fast.

Implementation Notes

• Handling city 1: Since city 1 is already visited from the start, it can be ignored even if it appears in a mission’s set \(S_j\). By only including cities other than city 1 in the target city list, you can save bits.

• Unreachable paths: If a city is unreachable via Dijkstra’s algorithm, initialize with a sufficiently large value (INF) and always check that the time limit \(T\) is not exceeded.

• Reward aggregation: Since multiple missions may have the same \(S_j\), make sure to add (accumulate) values when initially computing reward_direct.

  Source Code

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()

---

This editorial was generated by gemini-3-flash-thinking.