제출 #1299120

#제출 시각아이디문제언어결과실행 시간메모리
1299120kitsunoxVoting Cities (NOI22_votingcity)C++20
0 / 100
20 ms1084 KiB
    #include <bits/stdc++.h>
    using namespace std;
    #define state tuple<int,int,int,int,int,int,int>

    int votecity[5005];
    vector<pair<int,int>> mp[5005];

    int main(){
        int n,e,k;
        cin >> n >> e >> k;
        for(int i= 0;i < k;i++){
            cin >> votecity[i];
        }
        for(int i = 0 ;i < e;i++){
            int a,b,c;
            cin >> a >> b >> c;
            mp[a].push_back({b,c});
        }
        int q;
        cin >> q;
        //do the cal here
        while(q--){
            int s,p1,p2,p3,p4,p5;
            int t1 = 1,t2 = 1,t3 = 1,t4 = 1,t5 = 1;
            cin >> s >> p1 >> p2 >> p3 >> p4 >> p5;
            if(p1 == -1){
                t1 = 0;
            }
            if(p2 == -1){
                t2 = 0;
            }
            if(p3 == -1){
                t3 = 0;
            }
            if(p4 == -1){
                t4 = 0;
            }
            if(p5 == -1){
                t5 = 0;
            }
            priority_queue<state,vector<state>,greater<state>> pq;
            int vsmp[n+5][2][2][2][2][2];
            for(int i = 0;i < n;i++){
                for(int r1 = 0;r1 <= 1;r1++){
                    for(int r2 = 0;r2 <= 1;r2++){
                        for(int r3 = 0;r3 <= 1;r3++){
                            for(int r4 = 0;r4 <= 1;r4++){
                                for(int r5 = 0;r5 <= 1;r5++){
                                    vsmp[i][r1][r2][r3][r4][r5] = 1e9+5;
                                }
                            }
                        }
                    }
                }
            }
            vsmp[s][t1][t2][t3][t4][t5] = 0;
            pq.push({0,s,t1,t2,t3,t4,t5});
            while(!pq.empty()){
                auto [cost , town , te1 , te2 ,te3 ,te4 , te5 ] = pq.top();pq.pop();
                if(vsmp[town][te1][te2][te3][te4][te5] < cost)continue;
                for(auto [netown , necost] : mp[town]){
                    if(vsmp[town][te1][te2][te3][te4][te5]+necost < vsmp[netown][te1][te2][te3][te4][te5]){
                        vsmp[netown][te1][te2][te3][te4][te5] = vsmp[town][te1][te2][te3][te4][te5]+necost;
                        pq.push({vsmp[netown][te1][te2][te3][te4][te5],netown,te1,te2,te3,te4,te5});
                    }
                    if(te1 != 0 && vsmp[town][te1][te2][te3][te4][te5]+(necost*0.9)+p1 < vsmp[netown][0][te2][te3][te4][te5]){
                        vsmp[netown][0][te2][te3][te4][te5] = vsmp[town][te1][te2][te3][te4][te5]+(necost*0.9)+p1;
                        pq.push({vsmp[netown][0][te2][te3][te4][te5],netown,0,te2,te3,te4,te5});
                    }
                    if(te2 != 0 && vsmp[town][te1][te2][te3][te4][te5]+(necost*0.8)+p2 < vsmp[netown][te1][0][te3][te4][te5]){
                        vsmp[netown][te1][0][te3][te4][te5] = vsmp[town][te1][te2][te3][te4][te5]+(necost*0.8)+p2;
                        pq.push({vsmp[netown][te1][0][te3][te4][te5],netown,te1,0,te3,te4,te5});
                    }
                    if(te3 != 0 && vsmp[town][te1][te2][te3][te4][te5]+(necost*0.7)+p3 < vsmp[netown][te1][te2][0][te4][te5]){
                        vsmp[netown][te1][te2][0][te4][te5] = vsmp[town][te1][te2][te3][te4][te5]+(necost*0.7)+p3;
                        pq.push({vsmp[netown][te1][te2][0][te4][te5],netown,te1,te2,0,te4,te5});
                    }
                    if(te4 != 0 && vsmp[town][te1][te2][te3][te4][te5]+(necost*0.6)+p4 < vsmp[netown][te1][te2][te3][0][te5]){
                        vsmp[netown][te1][te2][te3][0][te5] = vsmp[town][te1][te2][te3][te4][te5]+(necost*0.6)+p4;
                        pq.push({vsmp[netown][te1][te2][te3][0][te5],netown,te1,te2,te3,0,te5});
                    }
                    if(te5 != 0 && vsmp[town][te1][te2][te3][te4][te5]+(necost*0.5)+p5 < vsmp[netown][te1][te2][te3][te4][0]){
                        vsmp[netown][te1][te2][te3][te4][0] = vsmp[town][te1][te2][te3][te4][te5]+(necost*0.5)+p5;
                        pq.push({vsmp[netown][te1][te2][te3][te4][0],netown,te1,te2,te3,te4,0});
                    }
                }
            }
            int mn = 1e9;
            for(int i = 0;i < k;i++){
                for(int r1 = 0;r1 <= 1;r1++){
                    for(int r2 = 0;r2 <= 1;r2++){
                        for(int r3 = 0;r3 <= 1;r3++){
                            for(int r4 = 0;r4 <= 1;r4++){
                                for(int r5 = 0;r5 <= 1;r5++){
                                    mn = min(mn,vsmp[votecity[i]][r1][r2][r3][r4][r5]);
                                    //cout << mn << ' ' << vsmp[votecity[i]][r1][r2][r3][r4][r5] << '\n';
                                }
                            }
                        }
                    }
                }
            }
            if(mn == 1e9)cout << "-1\n";
            else cout << mn << '\n';
        }
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...