Submission #1273002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273002		ken7236	Voting Cities (NOI22_votingcity)	C++20	100 / 100	73 ms	8352 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, e, k;
    cin>>n>>e>>k;
    vector<int> v(k);
    for(int a=0; a<k; a++)
    {
        cin>>v[a];
    }
    vector<vector<pair<int, int> > > g(n+1);
    for(int a = 0; a<e; a++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        g[v].push_back({u, c});
    }
    int dis[5005][32];
    for(int a=0; a<n; a++)
        for(int m=0; m<32; m++)
            dis[a][m] = LONG_LONG_MAX;
    priority_queue<pair<int, pair<int, int> > > pq;
    for(int a=0; a<k; a++)
    {
        dis[v[a]][0] = 0;
        pq.push({0, {v[a], 0}});
    }
    while(!pq.empty())
    {
        int d = - pq.top().first;
        int u = pq.top().second.first;
        int mask = pq.top().second.second;
        pq.pop();
        if(d != dis[u][mask])
            continue;
        for(int a=0; a<g[u].size(); a++)
        {
            int v = g[u][a].first;
            int w = g[u][a].second;
            int nd = d + w;
            if(nd < dis[v][mask])
            {
                dis[v][mask] = nd;
                pq.push({- nd, {v, mask}});
            }
            for(int t=0; t<5; t++)
            {
                if(mask & (1<<t))
                    continue;
                int nmask = mask | (1 << t);
                int nd2 = d + (w * (9-t)) / 10;
                if(nd2 < dis[v][nmask])
                {
                    dis[v][nmask] = nd2;
                    pq.push({ - nd2, {v,  nmask}});
                }
            }
        }
    }
    int q;
    cin>>q;
    while(q--)
    {
        int s;
        int p[5];
        cin>>s;
        int av = 0;
        for(int a=0; a<5; a++)
        {
            cin>>p[a];
            if(p[a] != -1)
                av |= (1<<a);
        }
        int ans = LONG_LONG_MAX;
        for(int m = 0; m < 32; m++)
        {
            if((m & ~av) != 0)
                continue;
            int base = dis[s][m];
            if(base >= LONG_LONG_MAX)
                continue;
            int sum = 0;
            for(int t= 0; t<5; t++)
            {
                if(m &(1<<t))
                    sum += p[t];
            }
            ans = min(ans, base + sum);
        }
        if(ans >= LONG_LONG_MAX)
            cout<<"-1\n";
        else
            cout<<ans<<endl;
    }
}

• 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