Overview

This problem involves starting from city 1 on a weighted directed graph, visiting several cities within a time limit \(T\), and maximizing the total reward from completed missions.

By noting that the total number of cities involved in missions is at most 14, we can efficiently find the optimal solution within the time limit by combining Dijkstra’s algorithm, Bit DP (an application of the Traveling Salesman Problem), and Sum over Subsets DP (SOS DP / Fast Zeta Transform).

---

Analysis

1. Narrowing Down Important Cities

Although the total number of cities \(N\) can be as large as \(10^4\), the total number of cities involved in mission conditions is at most 14 (\(\bigcup S_j \le 14\)). We define the set combining city 1 (the starting point) and all cities appearing in missions as the “important cities \(V_{\text{imp}}\)”. The number of important cities \(D = |V_{\text{imp}}|\) is at most \(15\).

To complete missions, we need to visit the important cities. Cities other than important cities only function as “waypoints” for traveling between important cities. Therefore, as long as we know the shortest travel times between important cities, we no longer need to directly search the original large graph.

2. Computing Shortest Distances Between Important Cities

We apply Dijkstra’s algorithm starting from each important city \(u \in V_{\text{imp}}\). Since the number of important cities is \(D \le 15\), running Dijkstra’s algorithm \(D\) times gives us the shortest distances between all pairs of important cities.

3. Exploring Visit Patterns with Bit DP

We manage the set of visited important cities using bits (mask). This is a setting very similar to the “Traveling Salesman Problem (TSP)” and can be solved with the following Bit DP:

• \(dp[mask][i]\) := the minimum travel time when the set of important cities visited so far is \(mask\) and we are currently at important city \(i\)

The initial state is being at city 1 (index 0) having visited only city 1, so \(dp[1][0] = 0\) and all others are \(\infty\). The transitions of this DP can be performed in \(O(2^D \cdot D^2)\) by exhaustively searching the next important city \(j\) to visit. Since \(D \le 15\), the number of states is \(2^{15} \times 15 \approx 5 \times 10^5\), which runs sufficiently fast.

After the DP is complete, for each \(mask\), those satisfying \(\min_{i} dp[mask][i] \le T\) represent “sets of cities that can be visited within the time limit \(T\)”.

4. Efficient Reward Calculation

Given a set of visited important cities \(mask\), we want to compute the total reward that can be obtained. Let \(mask_j\) be the bit representation of the city set \(S_j\) of mission \(j\). The obtainable reward is the sum of rewards \(P_j\) for all missions \(j\) satisfying “\(mask_j\) is a subset of \(mask\)” (\(mask \ \& \ mask_j = mask_j\)).

Computing this naively for all \(mask\) takes \(O(2^D \cdot K)\), which is fast enough, but using Sum over Subsets DP (SOS DP / Fast Zeta Transform) allows us to compute it more efficiently and elegantly in \(O(2^D \cdot D)\).

---

Algorithm

1. Extract Important Cities: Collect all cities appearing in missions and city 1 (the starting point), remove duplicates, and create the list of important cities \(V_{\text{imp}}\). Let \(D\) be the number of important cities.

2. Compute Shortest Distances Between Important Cities: Run Dijkstra’s algorithm from each important city \(v \in V_{\text{imp}}\) and construct the distance matrix dist_matrix (size \(D \times D\)).

3. Tour DP (Bit DP): Starting from city 1, find the shortest time to visit important cities using Bit DP. After updating \(dp[mask][i]\), for each \(mask\), determine whether the minimum time at any city \(i\) is at most \(T\), and record the reachable \(mask\) values.

4. Reward Accumulation via Fast Zeta Transform:

   • Prepare an array val (size \(2^D\)), and for each mission \(j\), add the reward \(P_j\) at the position of the bit representation \(mask_j\) of its required city set.
   • Perform the fast zeta transform to compute, for each \(mask\), “the sum of rewards for all \(mask_j\) that are subsets of \(mask\)”.

5. Obtain the Maximum Value: Output the maximum value of val[mask] among all reachable \(mask\) values.

---

Complexity

Time Complexity

• Dijkstra’s algorithm: Executed \(D\) times (once per important city), so \(O(D(N + M \log N))\).
• Bit DP: With \(2^D \cdot D\) states and \(D\) possible next transitions, \(O(2^D \cdot D^2)\).
• Fast Zeta Transform: \(O(2^D \cdot D)\).

The overall time complexity is \(O(D(N + M \log N) + 2^D \cdot D^2)\). With \(N, M \le 10^4, D \le 15\), the execution time is well under 0.1 seconds even in the worst case, which is very fast.

Space Complexity

• Graph adjacency list: \(O(N + M)\).
• Shortest distance matrix: \(O(D^2)\).
• DP table and cumulative sum array: \(O(2^D \cdot D)\).

The overall space complexity is \(O(N + M + 2^D \cdot D)\), which has plenty of margin with respect to the memory limit.

---

Implementation Notes

How the Fast Zeta Transform (SOS DP) Works

The following part of the code is the fast zeta transform that computes the cumulative sum over subsets.

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

By performing this operation, val[mask] correctly accumulates “the sum of rewards for subsets of mask (= missions achievable with only that set of cities)”. This allows us to look up the maximum reward obtainable for each \(mask\) in \(O(1)\).

Source Code

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

---

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