Submission #750969

#	Time	Username	Problem	Language	Result	Execution time	Memory
750969		dsyz	Voting Cities (NOI22_votingcity)	C++17	100 / 100	77 ms	8252 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (5005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,E,K;
	cin>>N>>E>>K;
	vector<pair<ll,ll> > v[N];
	ll votingcities[K];
	for(ll i = 0;i < K;i++){
		cin>>votingcities[i];
	}
	for(ll i = 0;i < E;i++){
		ll a,b,c;
		cin>>a>>b>>c;
		v[b].push_back({a,c}); 
		//reverse the edges as we start from votingcities
	}
	priority_queue<pair<ll,pair<ll,ll> >,vector<pair<ll,pair<ll,ll> > >,greater<pair<ll,pair<ll,ll> > > > pq;
	ll dist[N][32]; //(1<<5) = 32 (11111 is 31 so 31 is max index)
	memset(dist,-1,sizeof(dist));
	for(ll k = 0;k < K;k++){
		ll x = votingcities[k];
		for(ll j = 0;j < 32;j++){
			dist[x][j] = 0;
			pq.push({dist[x][j],{x,j}});
		}
	}
	while(!pq.empty()){
		ll d = pq.top().first;
		ll x = pq.top().second.first;
		ll used = pq.top().second.second; //tickets used so far
		pq.pop();
		if(d != dist[x][used]){
			continue;
		}
		vector<ll> left;
		for(ll i = 0;i < 5;i++){
			if(!((1<<i) & used)){
				left.push_back(i);
			}
		}
		for(auto u : v[x]){
			if(dist[u.first][used] == -1 || dist[u.first][used] > dist[x][used] + u.second){
				dist[u.first][used] = dist[x][used] + u.second;
				pq.push({dist[u.first][used],{u.first,used}});
			}
			for(auto ticket : left){
				ll bitadd = 1<<ticket;
				if(dist[u.first][used + bitadd] == -1 || 
				dist[u.first][used + bitadd] > dist[x][used] + 
				(u.second - (((ticket + 1) * u.second) / 10))){
					dist[u.first][used + bitadd] = dist[x][used] + (u.second - (((ticket + 1) * u.second) / 10));
					pq.push({dist[u.first][used + bitadd],{u.first,used + bitadd}});
				}
			}
		}
	}
	ll Q;
	cin>>Q;
	for(ll q = 0;q < Q;q++){
		ll S;
		ll P[5];
		cin>>S>>P[0]>>P[1]>>P[2]>>P[3]>>P[4];
		ll minimum = 1e18;
		for(ll bitmask = 0;bitmask < (1<<5);bitmask++){
			//when bitmask = 0, it is 00000 (no tickets used)
			bool can = 1;
			for(ll i = 0;i < 5;i++){
				if(((1<<i) & bitmask) && P[i] == -1){
					can = 0;
				}
			}
			if(!can) continue;
			ll addcost = 0;
			for(ll i = 0;i < 5;i++){
				if((1<<i) & bitmask){
					addcost += P[i];
				}
			}
			if(dist[S][bitmask] == -1) continue;
			minimum = min(minimum,dist[S][bitmask] + addcost);
		}
		if(minimum >= 1e18) cout<<-1<<'\n';
		else cout<<minimum<<'\n';
	}
}

• 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