Submission #864718

#TimeUsernameProblemLanguageResultExecution timeMemory
864718TAhmed33Parkovi (COCI22_parkovi)C++98
10 / 110
48 ms448 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int n, k; vector <pair <int, int>> adj[25]; int dist[20]; void dfs (int pos, int par = -1, int dep = 0) { dist[pos] = min(dist[pos], dep); for (auto j : adj[pos]) { if (j.first != par) { dfs(j.first, pos, dep + j.second); } } } signed main () { cin >> n >> k; for (int i = 1; i < n; i++) { int a, b, w; cin >> a >> b >> w; a--; b--; adj[a].push_back({b, w}); adj[b].push_back({a, w}); } int mn = 1e16; vector <int> ans; for (int i = 0; i < (1 << n); i++) { if (__builtin_popcount(i) == k) { for (int j = 0; j < n; j++) { dist[j] = 1e16; } for (int j = 0; j < n; j++) { if (i & (1 << j)) { dfs(j); } } int mx = 0; for (int j = 0; j < n; j++) mx = max(mx, dist[j]); if (mx < mn) { vector <int> p; for (int j = 0; j < n; j++) { if (i & (1 << j)) { p.push_back(j + 1); } } mn = mx; ans = p; } } } cout << mn << '\n'; for (auto i : ans) cout << i << " "; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...