Submission #1340619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340619		ggezlolx3d	Voting Cities (NOI22_votingcity)	C++20	100 / 100	251 ms	4896 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX 1e15
signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n,m,i,j,nn,t,st,en,q,mon,k;
    cin >> n >> m >> en;
    vector<int> jj(en);
    for(i=0;i<en;i++){
        cin >> jj[i];
    }
    vector<pair<int,int>> arr[n+1];
    for(i=0;i<m;i++){
        int x,y,z;
        cin >> x >> y >> z;
        arr[x].push_back({z,y});
    }
    cin >> q;
    while(q--){
        cin >> st;
        vector<int> tua;
        for(i=0;i<5;i++){
            cin >> nn;

            tua.push_back(nn);
        }
        //cout << tua[4] << "\n\n\n";
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
        pq.push({0,{st,0}});
        vector<vector<int>> di(n,vector<int>(32,INT_MAX));
        vector<vector<int>> vi(n,vector<int>(32,false));
        di[st][0]=0;
        while(!pq.empty()){
            int x=pq.top().first;
            int y=pq.top().second.first;
            int z=pq.top().second.second;
            pq.pop();

            if(vi[y][z])continue;
            vi[y][z]=true;
            if(x>di[y][z])continue;
            for(pair<int,int> U:arr[y]){
                int u=U.first;
                int v=U.second;
                if(!vi[v][z]){
                    if(di[y][z]+u<di[v][z]){

                        di[v][z]=di[y][z]+u;
                        pq.push({di[v][z],{v,z}});
                    }
                }
                for(i=0;i<5;i++){
                    int aaa=1<<i;
                    if(tua[i]==-1)continue;
                    if(!(z&aaa)){
                        if(tua[i]>=u*((i+1)*0.1)){
                            continue;
                        }
                        int sss=z|aaa;
                        int dis=di[y][z]+u*(1-(i+1)*0.1)+tua[i];

                        if(dis<di[v][sss]){//cout << y << " " << i << " " << tua[i] << "\n";
                            di[v][sss]=dis;
                            pq.push({di[v][sss],{v,sss}});
                        }

                    }
                }

            }
        }
        int ans=INT_MAX;
        for(i=0;i<en;i++){
            for(j=0;j<32;j++){
                ans=min(ans,di[jj[i]][j]);
            }
        }
        if(ans==INT_MAX){
            cout << -1 << "\n";
            continue;
        }
        else{
            cout << ans << "\n";
        }
    }
}
/*
5 18 30
1 2 93 84 2
*/

Compilation message (stderr)

Main.cpp:4: warning: "INT_MAX" redefined
    4 | #define INT_MAX 1e15
      | 
In file included from /usr/include/c++/13/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:38,
                 from Main.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/13/include/limits.h:120: note: this is the location of the previous definition
  120 | #define INT_MAX __INT_MAX__
      |

• 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