Submission #1306465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306465		Zone_zonee	Voting Cities (NOI22_votingcity)	C++20	45 / 100	1094 ms	5652 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e3+10;

vector<int> cities;
vector<pair<int, ll>> adj[N];
ll dijkstra(int st, int *p){
    ll dist[1<<5][N];
    memset(dist, 0x3f, sizeof dist);
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
    int init_state = 0;
    for(int i = 1; i <= 5; ++i) if(p[i] != -1) init_state |= (1<<(i-1));
    pq.push({dist[init_state][st] = 0, st, init_state});
    while(!pq.empty()){
        auto [d, u, state] = pq.top(); pq.pop();
        if(d > dist[state][u]) continue;
        for(auto [v, w] : adj[u]){
            for(int i = 0; i < 5; ++i){
                if(!(state&(1<<i))) continue;
                if(dist[state^(1<<i)][v] > d+w*(9-i)/10 + p[i+1]){
                    pq.push({dist[state^(1<<i)][v] = d+w*(9-i)/10 + p[i+1], v, state^(1<<i)});
                }
            }
            if(dist[state][v] > d+w){
                pq.push({dist[state][v] = d+w, v, state});
            }
        }
    }
    ll ans = 0x3f3f3f3f3f3f3f3f;
    for(int c : cities){
        for(int i = 0; i < 32; ++i) ans = min(ans, dist[i][c]);
    }
    return (ans == 0x3f3f3f3f3f3f3f3f ? -1 : ans);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1, x; i <= k; ++i){
        cin >> x;
        cities.push_back(x);
    }
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    int q;
    cin >> q;
    while(q--){
        int s, p[6];
        cin >> s;
        for(int i = 1; i <= 5; ++i) cin >> p[i];
        cout << dijkstra(s, p) << '\n';
    }
}

• 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