oj.uz

답안 #380260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380260 2021-03-20T18:00:02 Z ritul_kr_singh Kronican (COCI16_kronican) C++17
20 / 100
 2000 ms 492 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 42 ms 376 KB Output isn't correct
6 Incorrect 40 ms 492 KB Output isn't correct
7 Incorrect 221 ms 364 KB Output isn't correct
8 Incorrect 393 ms 384 KB Output isn't correct
9 Incorrect 76 ms 364 KB Output isn't correct
10 Execution timed out 2078 ms 364 KB Time limit exceeded