思路是是先最小生成树
然后二分答案，
check就是每个点跑dfs能跑过就是true否则false
然后就挂90了，WA的点是k=1
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=11451;
int n,m,k;
int f[114],edcnt;
int head[N],cnt;
int l,r,mid,vis[114];
struct node{
int u,v,w;
}ed[N];
struct edge{
int to,next,w;
}e[N];
void add_edge(int u,int v,int w){
e[++cnt].to=v;
e[cnt].next=head[u];
e[cnt].w=w;
head[u]=cnt;
}
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
bool cmp(node x,node y){
return x.w<y.w;
}
void kruskal(){
for(int i=1;i<=m;i++){
int fu=find(ed[i].u),fv=find(ed[i].v);
if(fu==fv) continue;
f[fv]=fu;
add_edge(ed[i].u,ed[i].v,ed[i].w);
add_edge(ed[i].v,ed[i].u,ed[i].w);
//cout<<ed[i].u<<" "<<ed[i].v<<endl;
if(++edcnt==n-1) return;
}
}
void dfs(int u,int fa,int kcnt,int cntd,int d){//剩余次数,剩余魔法，魔法上线
if(vis[u]||kcnt<0) return;
vis[u]=1;
//cout<<u<<endl;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(v==fa||d<w) continue;
if(kcnt==0&&cntd<w) continue;
//cerr<<u<<" "<<v<<" "<<kcnt<<" "<<cntd<<endl;
if(cntd>=w) dfs(v,u,kcnt,cntd-w,d);//还能走完
else if(kcnt>0) dfs(v,u,kcnt-1,d-w,d);//需要换魔力
}
}
bool check(int x){
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
//cout<<"check:"<<i<<endl;
dfs(i,i,k,0,x);
for(int j=1;j<=n;j++){
if(!vis[j]) return false;
}
}
return true;
}
signed main(){
freopen("portal.in","r",stdin);
freopen("portal.out","w",stdout);
cin>>n>>m>>k;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++) cin>>ed[i].u>>ed[i].v>>ed[i].w;
sort(ed+1,ed+m+1,cmp);
kruskal();
l=1;r=1e18;
while(l<r){
mid=(l+r)>>1;
cerr<<mid<<endl;
if(check(mid)){
r=mid;
}
else l=mid+1;
}
cout<<l;
return 0;
}
//