Submission #1184820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184820		asli_bg	Voting Cities (NOI22_votingcity)	C++20	20 / 100	77 ms	840 KiB

Main

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

#define int long long

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<bool> vb;

#define fi first
#define se second
#define pb push_back

#define mid (l+r)/2
#define all(x) x.begin(),x.end()
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
#define sp <<" "<<

#define DEBUG(x) cout<<(#x) sp x<<endl

const int INF=1e18;
const int MAXN=5e3+5;

int n,e,k;

vii adj[MAXN];
bool mark[MAXN];

int p[10];
int d[MAXN];

int bfs(int bas){
    set<pii> s;
    s.insert({0,bas});
    FORE(i,1,n+1) d[i]=INF;
    d[bas]=0;

    int res=INF;

    while(!s.empty()){
        auto el=*s.begin();
        s.erase(el);

        int nd=el.se;

        if(mark[nd]) res=min(res,d[nd]);

        for(auto [kom,cost]:adj[nd]){
            if(d[kom]>d[nd]+cost){
                if(d[kom]!=INF) s.erase({d[kom],kom});
                d[kom]=d[nd]+cost;
                s.insert({d[kom],kom});
            }
        }
    }

    return (res==INF?-1:res);
}

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

    cin>>n>>e>>k;
    vi tt(k+1);
    FORE(i,1,k+1){
        cin>>tt[i];
        tt[i]++;
        mark[tt[i]]=true;
    }

    FOR(i,e){
        int a,b,c;
        cin>>a>>b>>c;
        a++;b++;
        adj[a].pb({b,c});
    }

    int q;
    cin>>q;
    while(q--){
        int s;
        cin>>s>>p[1]>>p[2]>>p[3]>>p[4]>>p[5];

        s++;

        cout<<bfs(s)<<endl;
    }
}

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