#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
vector<int> e;
int get(int u){
return e[u] < 0 ? u : e[u] = get(e[u]);
}
bool unite(int u, int v){
u = get(u), v = get(v);
if(u==v) return false;
if(e[u] > e[v]) swap(u, v);
e[u] += e[v], e[v] = u;
return true;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, k; cin >> n >> k;
int d[n][n];
vector<array<int, 3>> edges;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
cin >> d[i][j];
}
}
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j){
edges.push_back({min(d[i][j], d[j][i]), i, j});
}
}
sort(edges.begin(), edges.end());
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;
e.assign(n, -1);
int first = -1, res = 0;
for(int j=0; j<n; ++j) if((1<<j)&i) first = j;
for(int j=0; j<n; ++j) if((1<<j)&i) unite(j, first);
for(auto edge : edges){
if(unite(edge[1], edge[2])) res += edge[0];
}
ans = min(ans, res);
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 7 |
Incorrect |
15 ms |
364 KB |
Output isn't correct |
| 8 |
Incorrect |
27 ms |
364 KB |
Output isn't correct |
| 9 |
Incorrect |
24 ms |
364 KB |
Output isn't correct |
| 10 |
Incorrect |
219 ms |
364 KB |
Output isn't correct |
