oj.uz

Submission #380258

# Submission time Handle Problem Language Result Execution time Memory
380258 2021-03-20T17:46:13 Z ritul_kr_singh Kronican (COCI16_kronican) C++17
30 / 100
 309 ms 384 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;

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 7 ms 384 KB Output isn't correct
6 Incorrect 6 ms 376 KB Output isn't correct
7 Incorrect 31 ms 364 KB Output isn't correct
8 Incorrect 51 ms 364 KB Output isn't correct
9 Incorrect 28 ms 364 KB Output isn't correct
10 Correct 309 ms 364 KB Output is correct