Submission #1289324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289324		nikulid	Cities (BOI16_cities)	C++20	14 / 100	543 ms	23576 KiB

cities

// all I did was make stuff long long
#include <bits/stdc++.h> 

using namespace std;

bool debug=0;
#define dout if(debug)cout

#define ll long long
#define pb push_back
#define mp make_pair

int main(){
	ll n,k,m;
	cin>>n>>k>>m;
	vector<ll> ks(k);
	for(int i=0; i<k; i++){
		cin>>ks[i];
		--ks[i];
	}
	vector<vector<pair<ll, ll>>> adj(n);
	ll u,v,c;
	for(int i=0; i<m; i++){
		cin>>u>>v>>c;
		--u;--v;
		adj[u].pb({v,c});
		adj[v].pb({u,c});
	}
	dout<<"--input done--\n";
	
	// case where k <= 3
	// in the ideal configuration, there exists a node such that each important city has a direct path to that node
	
	vector<vector<ll>> dist(n, vector<ll>(k,-1));
	// we must do dijkstra to get the min dist from each node to each important city
	priority_queue<pair<ll, ll>> q;
	ll cur_node, cur_dist;
	for(int i=0; i<k; i++){
		// do dijkstra from the k-th important city
		dout<<"--pushing to q--\n";
		q.push({0, ks[i]});
		while(!q.empty()){
			cur_dist = -(q.top().first);
			cur_node = q.top().second;
			q.pop();
			if(dist[cur_node][i] != -1) continue; // already visitted
			dout<<"--not continued--\n";
			dist[cur_node][i] = cur_dist;
			for(pair<ll, ll> p:adj[cur_node]){
				q.push({-(cur_dist+p.second), p.first});
			}
		}
		dout<<"--dijkstra for "<<i<<"-th important city is done!\n";
	}
	// dijkstra should be done..
	dout<<"--dijkstra done--\n";
	// for k <= 3 it's just finding the node with minimum sum of distances
	ll best_sum=0, cur_sum;
	for(int j=0; j<k; j++){
		best_sum += dist[0][j];
	}
	for(int i=1; i<n; i++){
		cur_sum=0;
		for(int j=0; j<k; j++){
			cur_sum += dist[i][j];
		}
		if(cur_sum < best_sum){
			dout<<"new best sum at node "<<i<<": "<<cur_sum<<"!\n";
			best_sum = cur_sum;
		}
	}
	cout<<best_sum<<"\n";
	return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26