Submission #380260

#	Time	Username	Problem	Language	Result	Execution time	Memory
380260		ritul_kr_singh	Kronican (COCI16_kronican)	C++17	20 / 100	2078 ms	492 KiB

kronican

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n, k; cin >> n >> k;
	int d[n][n];
	for(int i=0; i<n; ++i){
		for(int j=0; j<n; ++j){
			cin >> d[i][j];
		}
	}

	int ans = 1e18;
	for(int i=0; i<(1<<n); ++i){
		int cnt = 0;
		for(int j=0; j<n; ++j) cnt += (bool)((1<<j)&i);
		if(cnt != k) continue;

		int res = 0;
		vector<bool> vis(n, false);
		priority_queue<array<int, 3>> q;
		for(int j=0; j<n; ++j){
			if((1<<j)&i){
				vis[j] = true;
				for(int v=0; v<n; ++v) q.push({-d[v][j], v, j});
			}
		}

		while(!q.empty()){
			int dist = -q.top()[0], v = q.top()[1], u = q.top()[2];
			q.pop();
			if(!vis[v]){
				vis[v] = true;
				for(int w=0; w<n; ++w) q.push({-d[w][v], w, v});
				res += dist;
			}
		}

		ans = min(ans, res);
	}
	cout << ans;
}

Compilation message (stderr)

kronican.cpp: In function 'int main()':
kronican.cpp:34:44: warning: unused variable 'u' [-Wunused-variable]
   34 |    int dist = -q.top()[0], v = q.top()[1], u = q.top()[2];
      |                                            ^

• Subtask 1: 20 / 100