Submission #1184924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184924		asli_bg	Voting Cities (NOI22_votingcity)	C++20	45 / 100	1095 ms	7608 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;
const int MAXK=35;

int n,e,k;

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

int p[10];
int d[MAXN][MAXK];
bool vis[MAXN][MAXK];

int dij(int bas){
    priority_queue<pair<int,pii>> s;
    s.push({0,{bas,0}});

    FORE(i,1,n+1){
        for(int j=0;j<(1<<5);j++){
            d[i][j]=INF;
            vis[i][j]=false;
        }
    }

    d[bas][0]=0;

    int res=INF;

    while(!s.empty()){
        auto el=s.top();
        s.pop();

        int nd=el.se.fi;
        int mask=el.se.se;

        if(vis[nd][mask]) continue;
        vis[nd][mask]=true;

        if(mark[nd]){
            res=d[nd][mask];
            break;
        }

        for(auto [kom,cost]:adj[nd]){
            //ticket kullanma
            if(d[kom][mask]>d[nd][mask]+cost){
                d[kom][mask]=d[nd][mask]+cost;
                s.push({-d[kom][mask],{kom,mask}});
            }

            //ticket kullan
            for(int bt=0;bt<5;bt++){
                if(mask&(1<<bt)) continue; //zaten kullandıysam ticketi
                if(p[bt+1]==-1) continue; //böyle bir ticket yoksa

                int yeni=mask+(1<<bt);
                int cost2=cost*(10-(bt+1))/10+p[bt+1];

                //DEBUG(cost);
                //DEBUG(cost2);

                if(d[kom][yeni]>d[nd][mask]+cost2){
                    d[kom][yeni]=d[nd][mask]+cost2;
                    s.push({-d[kom][yeni],{kom,yeni}});
                }
            }
        }
    }

    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<<dij(s)<<endl;
    }
}

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