Submission #1272363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272363		rana_azka	Voting Cities (NOI22_votingcity)	C++20	100 / 100	136 ms	15128 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 5000;

int n, m;
int voting_cities;
vector<int> list_voting_cities;
vector<pair<int, int>> adj[MAXN+5];
int start;
int ticket[10];
int dist[MAXN+5][50];

void mulaidarinol(){}

void solve(){
    // INPUT
    cin >> n >> m >> voting_cities;
    for(int i = 1; i <= voting_cities; i++){
        int temp; cin >> temp;
        temp++;
        list_voting_cities.push_back(temp);
    }
    for(int i = 1; i <= m; i++){
        int u, v, w; cin >> u >> v >> w;
        u++; v++;
        adj[v].push_back({u, w});
    }

    // INITALIZE 
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 40; j++){
            dist[i][j] = INF;
        }
    }
    
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> dijkstra;
    // {dist, mask, cur}
    for(auto vc : list_voting_cities) dijkstra.push({0, 0, vc});
    while(!dijkstra.empty()){
        auto [cur_dist, cur_mask, cur] = dijkstra.top();
        dijkstra.pop();
        
        if(dist[cur][cur_mask] <= cur_dist) continue;
        dist[cur][cur_mask] = cur_dist;
        
        for(int bt = 0; bt <= 5; bt++){
            int mask = (1 << (bt - 1));
            if(bt == 0) mask = 0;
            if(cur_mask & mask) continue;
            
            for(auto [next, weight] : adj[cur]){
                int next_mask = cur_mask | mask;
                int next_dist = dist[cur][cur_mask] + (weight * (10 - bt)  / 10);
                
                if(dist[next][next_mask] <= next_dist) continue;
                
                dijkstra.push({next_dist, next_mask, next});
            }
        }
    }

    int q; cin >> q;
    while(q--){
        cin >> start; start++;
        for(int i = 1; i <= 5; i++) cin >> ticket[i];
        
        int ans = INF;
        for(int mask = 0; mask <= 40; mask++){
            int cost = dist[start][mask];
            bool ok = 1;

            for(int bt = 1; bt <= 5; bt++){
                if(mask & (1 << (bt-1))){
                    if(ticket[bt] == -1) ok = 0;
                    cost += ticket[bt];
                }
            }
            
            if(!ok) continue;

            ans = min(cost, ans);
        }

        if(ans == INF) ans = -1;
        
        cout << ans << endl;
    }

}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        // mulaidarinol();
        solve();
        // cerr << endl;
    }

    return 0;
}

/*
3 2 1
2
0 1 100
1 2 200
1
0 10 20 1000 2000 -1
=> 280

2 0 1
1
1
0 -1 -1 -1 -1 -1
=> -1

6 3 2
4 5
0 4 100
1 4 200
2 5 300
4
0 -1 -1 -1 -1 -1
1 20 40 10 100 4
2 1 2 3 4 0
3 0 -1 0 0 0
=> 100
=> 104
=> 150
=> -1
*/

• 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