floyd+枚举
看点:
1.floyd同时用数组p记录转移节点k,这样知道线段的端点u v就可以得到整条线段
2.任意一点c到线段a b的距离=(d[a][c]+d[c][b]-d[a][b])/2
3.枚举直径st en的所有子线段a b:
for(int a=en;a;a=p[st][a])
for(int b=a;b;b=p[st][b])
代码:
#include<iostream>
#include<cstring>
#define Size 305
using namespace std; int n,s;
int num=;
int ans=0x3f3f3f3f;
int d[Size][Size];
int p[Size][Size];
struct path{
int u,v;
}g[Size*Size];
int cnt=; int main(){
memset(d,0x3f,sizeof(d));
cin>>n>>s;
for(int i=;i<=n;i++)d[i][i]=;
int a,b,w;
for(int i=;i<n;i++){
cin>>a>>b>>w;
d[a][b]=d[b][a]=w;
p[a][b]=a; p[b][a]=b;
}
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
if(k==i)continue;
for(int j=;j<=n;j++){
if(k==j||i==j)continue;
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
p[i][j]=k;
num=max(num,d[i][j]);
}
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(d[i][j]==num){
g[++cnt].u=i; g[cnt].v=j;
}
}
}
for(int i=;i<=cnt;i++){
int st=g[i].u; int en=g[i].v;
//cout<<st<<' '<<en<<endl;
for(int a=en;a;a=p[st][a]){
for(int b=a;b;b=p[st][b]){
if(d[a][b]>s)break;
//cout<<" "<<a<<' '<<b<<" "<<endl;
int dis=;
for(int c=;c<=n;c++){dis=max(dis,(d[a][c]+d[c][b]-d[a][b])/);}
ans=min(ans,dis);
}
}
}
cout<<ans<<endl;
}