제출 #1185484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185484		NotLinux	Voting Cities (NOI22_votingcity)	C++20	100 / 100	325 ms	14508 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int inf = 1e18 + 7;
void solve(){
    int n,e,k;
    cin >> n >> e >> k;
    vector<int>voting(k);
    for(int i = 0;i<k;i++){
    	cin >> voting[i];
    }
    vector<pair<int,int>>graph[n];
    for(int i = 0;i<e;i++){
    	int u,v,w;
    	cin >> u >> v >> w;
    	graph[v].push_back({u,w});
    }
    int dist[n][32];
    memset(dist , -1 , sizeof(dist));
    priority_queue<array<int,3>>pq;// dist , node , state
    for(int i = 0;i<k;i++)
    	pq.push({0,voting[i],0});
    while(!pq.empty()){
    	auto tmp = pq.top();
    	pq.pop();
    	if(dist[tmp[1]][tmp[2]] != -1)continue;
    	dist[tmp[1]][tmp[2]] = -tmp[0];
    	// cout << tmp[1] << " " << bitset<5>(tmp[2]) << " : " << -tmp[0] << endl;
    	for(auto itr : graph[tmp[1]]){
    		// kullanmadan 
    		pq.push({tmp[0] - itr.second , itr.first , tmp[2]});
    		// i. bileti kullanip
    		for(int i = 0;i<5;i++){
    			if((tmp[2] & (1 << i)) == 0){
    				pq.push({tmp[0] - itr.second + (i+1) * itr.second / 10 , itr.first , tmp[2] ^ (1 << i)});
    			}
    		}
    	}
    }
    int q;
    cin >> q;
    while(q--){
    	int st , cost[5];
    	cin >> st;
    	for(int i = 0;i<5;i++)
    		cin >> cost[i];
    	int ans = inf;
    	for(int i = 0;i<32;i++){
    		if(dist[st][i] == -1)continue;
    		int localans = dist[st][i];
    		bool skiple = 0;
    		for(int j = 0;j<5;j++){
    			if(i & (1 << j)){
    				localans += cost[j];
    				if(cost[j] == -1)skiple = 1;
    			}
    		}
    		if(!skiple)
    			ans = min(ans , localans);
    	}
    	cout << (ans == inf ? -1 : ans) << '\n';
    }
    cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << 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