Submission #1289330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289330		nikulid	Cities (BOI16_cities)	C++20	14 / 100	883 ms	23768 KiB

cities

// all I did was make stuff long long
// edit: wow I didn't expect that to work...
#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";
	
	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;
		}
	}
	if(k<=3){
		cout<<best_sum<<"\n";
	}
	else if(k==4){
		// k=4
		// there are (at most) 2 distinct nodes with >=3 repaired paths each. 
		// these are the possibilities: 
		// 	[0] - 0,1,2,3
		// 	[1] - 0,1,2
		// 	[2] - 0,1,3
		//	[3] - 0,2,3
		//	[4] - 1,2,3
		// Furthermore, it's one of these (the one with min. sum):
		//	[0]
		//	[1]+[2]
		//	[1]+[3]
		//	[1]+[4]
		//	[2]+[3]
		//	[2]+[4]
		//	[3]+[4]
		// so yeah :D

		vector<ll> intersections(5, 1e18);
		intersections[0] = best_sum;
		// find [1]
		for(int i=0; i<n; i++){
			intersections[1]=min(best_sum, dist[i][0]+dist[i][1]+dist[i][2]);
		}
		// find [2]
		for(int i=0; i<n; i++){
			intersections[2]=min(best_sum, dist[i][0]+dist[i][1]+dist[i][3]);
		}
		// find [3]
		for(int i=0; i<n; i++){
			intersections[3]=min(best_sum, dist[i][0]+dist[i][2]+dist[i][3]);
		}
		// find [4]
		for(int i=0; i<n; i++){
			intersections[4]=min(best_sum, dist[i][1]+dist[i][2]+dist[i][3]);
		}
		// ok nice now we have intersections<> done let's gooo
		cout<<min(intersections[0], min(intersections[1]+intersections[2], min(intersections[1]+intersections[3], min(intersections[1]+intersections[4], min(intersections[2]+intersections[3], min(intersections[2]+intersections[4], intersections[3]+intersections[4]))))))<<"\n";

	} else{
		cout<<"I don't know.\n";
	}
	return 0;
}

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