This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define endl "\n"
using namespace std;
ll n,m,k,l,i,j,q,x,y,z,ans,an,a[209][209],pr[200009];
vector<vector<pair<ll,ll> > > v(100009);
vector<ll> w;
void DF(ll i,ll kol,ll pred)
{
a[q][i]=kol; a[i][q]=kol;
for (auto u : v[i])
if (u.f!=pred)
{
DF(u.f,kol+u.s,i);
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >>n>>m;
for (i=1;i<n;i++)
{
cin >>x>>y>>z;
v[x].pb({y,z});
v[y].pb({x,z});
}
for (i=1;i<=n;i++)
{
q=i;
DF(i,0,-1);
}
l=(1<<n)-1;
ans=1e18; an=0;
for (i=1;i<=l;i++)
{
if (__builtin_popcount(i)!=m) continue;
w.clear();
for (j=0;j<n;j++)
if (i & (1<<j)) w.pb(j+1);
x=0;
for (j=1;j<=n;j++)
{
k=1e9;
for (auto u : w)
if (a[j][u]<k) k=min(k,a[j][u]);
x=max(x,k);
}
if (x<ans) { ans=x; an=i; }
}
cout <<ans<<endl;
for (i=0;i<n;i++)
if (an & (1<<i)) cout <<i+1<<" ";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |