제출 #380258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380258		ritul_kr_singh	Kronican (COCI16_kronican)	C++17	30 / 100	309 ms	384 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;

		vector<int> curr(n, 1e18);
		vector<bool> vis(n, false);
		priority_queue<pair<int, int>> q;
		for(int j=0; j<n; ++j){
			if((1<<j)&i) q.emplace(0, j), curr[j] = 0, vis[j] = true;
		}

		while(!q.empty()){
			int u = q.top().second, dist = -q.top().first;
			q.pop();
			vis[u] = true;
			if(dist != curr[u]) continue;
			for(int v=0; v<n; ++v){
				if(u != v and d[v][u] < curr[v] and !vis[v]){
					curr[v] = d[v][u];
					q.emplace(-curr[v], v);
				}
			}
		}

		ans = min(ans, accumulate(curr.begin(), curr.end(), 0LL));
	}
	cout << ans;
}

• Subtask 1: 30 / 100