제출 #1272474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272474		lechaa	Voting Cities (NOI22_votingcity)	C++20	100 / 100	176 ms	12504 KiB

Main

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

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, e, k1; cin >> n >> e >> k1;
    vector<bool> spec(n);
    for(int i = 0; i < k1; i++){
        int h; cin >> h;
        spec[h] = true;
    }
    vector<vector<int>> dis(n, vector<int>(1<<5, 1e18));
    vector<vector<bool>> d(n, vector<bool>(1<<5));
    multiset<pair<int, pair<int, int>>> s;
    //time, type, node
    vector<vector<pair<int, int>>> g(n);
    for(int i = 0; i < e; i++){
        int a, b, c; cin >> a >> b >> c;
        g[b].push_back({a, c});
    }
    for(int i = 0; i < n; i++){
        if(spec[i]){
            s.insert({0, {0, i}});
            dis[i][0] = 0;
        }
    }
    while(s.size() > 0){
        int time = s.begin()->first;
        auto [type, k] = s.begin()->second;
        s.erase(s.begin());
        if(d[k][type]) continue;
        d[k][type] = true;
        for(auto [v, tm] : g[k]){
            for(int y = 0; y < 5; y++){
                int j = 1<<y;
                if((type&j) == 0){
                    int ntype = (type | j);
                    if(d[v][ntype]) continue;
                    if(dis[v][ntype] > time + ((tm/10) * (10-(y+1)))){
                        dis[v][ntype] = time + ((tm/10) * (10-(y+1)));
                        s.insert({dis[v][ntype], {ntype, v}});
                    }
                }
            }
            if(d[v][type]) continue;
            if(dis[v][type] > time + tm){
                dis[v][type] = time + tm;
                s.insert({dis[v][type], {type, v}});
            }
        }
    }
    int q; cin >> q;
    while(q--){
        vector<int> p(5);
        int st; cin >> st;
        for(int i = 0; i < 5; i++){
            cin >> p[i];
        }
        int mn = 1e18;
        for(int y = 0; y < 1<<5; y++){
            int sum = 0;
            for(int z = 0; z < 5; z++){
                if((y&(1<<z)) != 0){
                    if(p[z] == -1){
                        sum = 1e18;
                        break;
                    }
                    sum += p[z];
                }
            }
            mn = min(mn, sum + dis[st][y]);
        }
        if(mn == 1e18){
            mn = -1;
        }
        cout << mn << "\n";
    }
    return 0;
}

• 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