Submission #930374

#	Time	Username	Problem	Language	Result	Execution time	Memory
930374		vjudge1	Voting Cities (NOI22_votingcity)	C++17	45 / 100	1068 ms	10612 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);
    }

    int q;
    cin >> q;


    while (q--) {

        int source;
        cin >> source;
        int mask = 0;
        vector<long long> prices;

        for (int i = 0; i < 5; i++) {
            int x;
            cin >> x;
            if (x != -1) mask |= (1 << i);
            prices.push_back(x);
        }

        // totalCost, mask, source
        priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<>> pq;
        pq.push({0, {0, source}});

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

        long long answer = -1;

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

            if (visited[state.second][state.first]) continue;
            visited[state.second][state.first] = 1;
            dist[state.second][state.first] = totalCost;

            if (is_special[state.second]) {
                answer = totalCost;
                break;
            }

            for (auto [v, w]: g[state.second]) {
                if (!dist[v][state.first] || dist[v][state.first] > totalCost + w) {
                    pq.push({totalCost + w, {state.first, v}});
                }
            }

            for (int i = 0; i < 5; i++) {
                if (mask & (1 << i) && (!(state.first & (1 << i)))) {
                    for (auto [v, w]: g[state.second]) {
                        int newMask = state.first | (1 << i);
                        long long new_cost = 1LL * (w * 10 - w * (i + 1)) / 10LL + prices[i];


                        if (!visited[v][newMask] || dist[v][newMask] > totalCost + new_cost) {
                            pq.push({totalCost + new_cost, {newMask, v}});
                        }
                    }
                }
            }
        }

        cout << answer << endl;

    }
}

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