暴力枚举两个端点,BFS算偏心距。
有O(n)的做法,跪了
#include<bits/stdc++.h>
using namespace std;
const int maxn=305;
vector<pair<int,int> > g[maxn];
int n,s;
int vis[maxn],ins[maxn],d[maxn],Min=1e9;
void dfs (int x,int f,int dep) {
//确定y枚举x
if (dep>s) return;
ins[x]=1;
queue<int> q;
int Max=0;
for (int i=1;i<=n;i++) vis[i]=0;
for (int i=1;i<=n;i++) {
if (ins[i]) {
q.push(i);
vis[i]=1;
d[i]=0;
}
}
while (q.size()) {
int u=q.front();
q.pop();
for (pair<int,int> it:g[u]) {
int v=it.first;
if (vis[v]) continue;
q.push(v);
vis[v]=1;
d[v]=d[u]+it.second;
Max=max(Max,d[v]);
}
}
Min=min(Min,Max);
for (pair<int,int> it:g[x]) {
int y=it.first;
if (y==f) continue;
dfs(y,x,dep+it.second);
}
ins[x]=0;
}
int main () {
scanf("%d%d",&n,&s);
for (int i=1;i<n;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(make_pair(v,w));
g[v].push_back(make_pair(u,w));
}
for (int i=1;i<=n;i++) {
dfs(i,i,0);
}
printf("%d\n",Min);
}