Overview

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

By noting that the number of distinct city types involved in missions is at most \(14\), we can efficiently solve this problem by combining Dijkstra’s algorithm for computing shortest paths with bitmask DP (dynamic programming) similar to the Traveling Salesman Problem (TSP).

Analysis

1. Narrowing Down the “Important Cities” to Focus On

While the total number of cities \(N\) and roads \(M\) can be as large as \(10^4\), the total number of cities involved in mission conditions is \(\bigcup_{j=1}^{K} S_j \le 14\), which is very small. Even including city \(1\) as the starting point, there are at most 15 “important cities” whose visits we need to consider. All other cities function merely as “waypoints” for traveling between important cities.

Therefore, if we let the set of at most \(15\) important cities be \(V_{\text{imp}}\), the problem can be decomposed as follows: 1. Find the shortest travel time between any two cities in \(V_{\text{imp}}\). 2. Using the computed shortest travel times, determine which subsets of \(V_{\text{imp}}\) can be visited within the time limit \(T\).

2. Computing Shortest Distances Between Cities

Let the size of \(V_{\text{imp}}\) be \(V_{\text{size}}\) (\(V_{\text{size}} \le 15\)). The shortest distance from each important city to all other cities can be computed by running Dijkstra’s algorithm \(V_{\text{size}}\) times. This gives us the shortest travel time dist[u][v] for all \(u, v \in V_{\text{imp}}\).

3. Exploring Visitable Patterns with Bitmask DP

We manage the set of visited important cities as a bitmask (mask). Since \(V_{\text{size}} \le 15\), the total number of visit states is only \(2^{15} = 32768\).

We define the following dynamic programming (DP): - dp[mask][u]: The minimum travel time when the set of important cities visited so far is mask and we are currently at important city u.

The initial state is having visited only city 1 (let its index be start_idx) and being there. - dp[1 << start_idx][start_idx] = 0 - All other values are initialized to \(\infty\).

The transition considers moving from the current location \(u\) to an unvisited important city \(v\). - dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v])

4. Maximizing Rewards

After the DP computation is complete, for every mask, we determine whether that visit state is achievable within the time limit \(T\). Specifically, a mask is achievable if \(\min_{u} \text{dp[mask][u]} \le T\) is satisfied.

For each achievable mask, we use bitwise operations to determine which missions are completed, calculate the total reward obtained, and the maximum among these is the answer.

Algorithm

1. Enumerating Important Cities and Coordinate Compression Collect all cities involved in each mission along with city \(1\), remove duplicates, and create the array \(V_{\text{imp}}\). Convert each city number to an index within \(V_{\text{imp}}\) (from \(0\) to \(V_{\text{size}} - 1\)) via coordinate compression, and also convert each mission’s condition \(S_j\) to a bitmask mission_mask[j].

2. Computing Shortest Paths Run Dijkstra’s algorithm starting from each city in \(V_{\text{imp}}\), a total of \(V_{\text{size}}\) times, to build the adjacency matrix dist between important cities.

3. Executing the Bitmask DP Update dp[mask][u] according to the transition formula described above.

4. Tallying the Answer For each mask, if it is reachable within the time limit \(T\), compute the obtainable reward and update the maximum. Whether mission \(j\) is completed can be determined by checking (mask & mission_mask[j]) == mission_mask[j].

Complexity

Time Complexity

• Dijkstra’s algorithm: \(O(V_{\text{size}} \cdot (N + M) \log N)\) Since \(V_{\text{size}} \le 15\), this part is sufficiently fast.
• Bitmask DP: \(O(2^{V_{\text{size}}} \cdot V_{\text{size}}^2)\) When \(V_{\text{size}} = 15\), the maximum number of loop iterations for state transitions is approximately \(32768 \times 15^2 \approx 7.3 \times 10^6\), well within the time limit.
• Reward tallying: \(O(2^{V_{\text{size}}} \cdot K)\) At most approximately \(32768 \times 100 \approx 3.2 \times 10^6\) checks.

The overall time complexity is \(O(V_{\text{size}} (N + M) \log N + 2^{V_{\text{size}}} (V_{\text{size}}^2 + K))\), which runs sufficiently fast for the typical time limit (2.0 seconds).

Space Complexity

• Graph adjacency list: \(O(N + M)\)
• Distance table between important cities dist: \(O(V_{\text{size}}^2)\)
• DP table dp: \(O(2^{V_{\text{size}}} \cdot V_{\text{size}})\)

The overall space complexity is \(O(N + M + 2^{V_{\text{size}}} \cdot V_{\text{size}})\). Since \(V_{\text{size}} \le 15\), memory usage stays within a few megabytes.

Implementation Notes

• Don’t forget to add city 1: Even if city 1 is not included in any mission, it is the starting point and is always visited first, so it must be included in the important city list \(V_{\text{imp}}\).

• Be careful with data types: The travel time \(T\), rewards \(P_j\), and accumulated shortest distances can become very large, so use long long type in C++.

• Coordinate compression: By using std::lower_bound, you can easily and efficiently convert original city numbers to \(0\)-indexed positions within \(V_{\text{imp}}\).

  Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

const long long INF = 1e18;

vector<long long> dijkstra(int start, const vector<vector<pair<int, long long>>>& adj, int N) {
    vector<long long> dist(N + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            long long w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    long long T;
    if (!(cin >> N >> M >> K >> T)) return 0;

    vector<vector<pair<int, long long>>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    vector<vector<int>> S(K);
    vector<long long> P(K);
    set<int> imp_set;
    for (int j = 0; j < K; ++j) {
        int sz;
        cin >> sz;
        S[j].resize(sz);
        for (int i = 0; i < sz; ++i) {
            cin >> S[j][i];
            imp_set.insert(S[j][i]);
        }
        cin >> P[j];
    }

    imp_set.insert(1);

    vector<int> V_imp(imp_set.begin(), imp_set.end());
    int V_size = V_imp.size();

    int start_idx = lower_bound(V_imp.begin(), V_imp.end(), 1) - V_imp.begin();

    vector<int> mission_mask(K, 0);
    for (int j = 0; j < K; ++j) {
        int mask = 0;
        for (int u : S[j]) {
            int idx = lower_bound(V_imp.begin(), V_imp.end(), u) - V_imp.begin();
            mask |= (1 << idx);
        }
        mission_mask[j] = mask;
    }

    vector<vector<long long>> dist(V_size, vector<long long>(V_size, INF));
    for (int i = 0; i < V_size; ++i) {
        auto d = dijkstra(V_imp[i], adj, N);
        for (int j = 0; j < V_size; ++j) {
            dist[i][j] = d[V_imp[j]];
        }
    }

    vector<vector<long long>> dp(1 << V_size, vector<long long>(V_size, INF));
    dp[1 << start_idx][start_idx] = 0;

    for (int mask = 1; mask < (1 << V_size); ++mask) {
        for (int u = 0; u < V_size; ++u) {
            if (dp[mask][u] >= INF) continue;
            for (int v = 0; v < V_size; ++v) {
                if (dist[u][v] >= INF) continue;
                if (!((mask >> v) & 1)) {
                    int next_mask = mask | (1 << v);
                    if (dp[next_mask][v] > dp[mask][u] + dist[u][v]) {
                        dp[next_mask][v] = dp[mask][u] + dist[u][v];
                    }
                }
            }
        }
    }

    long long max_reward = 0;
    for (int mask = 0; mask < (1 << V_size); ++mask) {
        bool reachable = false;
        for (int u = 0; u < V_size; ++u) {
            if (dp[mask][u] <= T) {
                reachable = true;
                break;
            }
        }
        if (!reachable) continue;

        long long reward = 0;
        for (int j = 0; j < K; ++j) {
            if ((mask & mission_mask[j]) == mission_mask[j]) {
                reward += P[j];
            }
        }
        max_reward = max(max_reward, reward);
    }

    cout << max_reward << "\n";

    return 0;
}

---

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