Submission #1340532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340532		ggezlolx3d	Voting Cities (NOI22_votingcity)	C++20	0 / 100	27 ms	756 KiB

Main

#include<bits/stdc++.h>
using namespace std;
//#define int long long
int dp[5000][5000];
signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n,m,i,j,nn,t,st,en,q,mon,ans=0,k;
    cin >> n >> m >> en;
    int jj[en];
    for(i=0;i<en;i++){
        cin >> jj[i];
    }
    vector<pair<int,int>> arr[n];
    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;
            if(nn==-1){
                continue;
            }
            tua.push_back(nn);
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        pq.push({0,st});
        vector<bool> vi(n,false);
        vector<int> di(n,INT_MAX);
        di[st]=0;
        vi[st]=true;
        while(!pq.empty()){
            int x=pq.top().first;
            int y=pq.top().second;
            pq.pop();
            for(auto [u,v]:arr[y]){
                if(vi[v])continue;
                vi[v]=true;
                if(di[y]+u<di[v]){
                    di[v]=di[y]+u;
                    pq.push({di[v],v});
                }
            }
        }
        int ans=INT_MAX;
        for(i=0;i<en;i++){
            ans=min(ans,di[jj[i]]);
        }
        if(ans==INT_MAX){
            cout << -1 << "\n";
            continue;
        }
        else{
            cout << ans << "\n";
        }
    }
}
/*
5 18 30
1 2 93 84 2
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 50