Submission #930418

#	Time	Username	Problem	Language	Result	Execution time	Memory
930418		vjudge1	Voting Cities (NOI22_votingcity)	C++17	100 / 100	118 ms	11968 KiB

Main

#include <bits/stdc++.h>

using namespace std;


signed main() {

    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    int n, e, special;
    cin >> n >> e >> special;

    vector<bool> is_special(n, false);
    for (int i = 0; i < special; i++) {
        int x;
        cin >> x;
        is_special[x] = true;
    }

    vector<vector<pair<int, long long>>> g(n), rev_g(n);

    for (int i = 0; i < e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        rev_g[v].emplace_back(u, w);
    }

    vector<vector<long long>> dist(n, vector<long long>((1 << 5) + 1, 0));
    vector<vector<bool>> visited(n, vector<bool>((1 << 5) + 1, 0));

    priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<>> pq;
    // totalCost, mask, node

    for (int i = 0; i < n; i++)
        if (is_special[i]) {
            pq.push({0, {0, i}});
        }

    while (!pq.empty()) {
        auto [totalCost, state] = pq.top();
        pq.pop();

        auto [mask, node] = state;

        if (visited[node][mask]) continue;
        visited[node][mask] = true;

        dist[node][mask] = totalCost;

        for (auto [v, w]: rev_g[node]) {
            for (int bit = 0; bit < 5; bit++) {
                bool isSet = mask & (1 << bit);
                if (isSet) continue;

                int newMask = mask | (1 << bit);

                if (visited[v][newMask]) continue;

                long long newPrice = (w * 10 - w * (bit + 1)) / 10 + totalCost;

                if (!visited[v][newMask]) {
                    pq.push({newPrice, {newMask, v}});
                }
            }
        }

        for (auto [v, w]: rev_g[node]) {
            if (visited[v][mask]) continue;
            long long newPrice = w + totalCost;
            pq.push({newPrice, {mask, v}});
        }
    }


    int q;
    cin >> q;

    while (q--) {
        int src;
        cin >> src;

        vector<int> ticket_price(5);
        for (int i = 0; i < 5; i++) cin >> ticket_price[i];


        long long ans = 1e16;


        for (long long i = 0, tmp = 0; i < (1 << 5); i++) {
            if (visited[src][i]) {
                for (int j = 0; j < 5; j++) {
                    if (i & (1 << j)) {
                        if (ticket_price[j] == -1) {
                            tmp = 1e16;
                            break;
                        } else tmp += ticket_price[j];
                    }
                }
                ans = min(ans, tmp + dist[src][i]);
            }

            tmp = 0;
        }

        if (ans >= 1e16) cout << -1 << '\n';
        else cout << ans << '\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 50 / 50