题目链接
题目思路
这个题目的思路就是连\(1,j\)一个长度为\(x\)的边
其实就是有个中转点
\(dep[i]=min(dis[1][i],dis[i][j]+x)\)
那么如果\(x\leq dis[1][i]-dis[i][j]\;dep[i]=dis[i][j]+x\) 反之亦然
对于中转点利用双指针的思想写写
说的感觉好差,看代码可能可以看懂
代码
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn=3e3+5;
int n;
int pr[maxn];
int dis[maxn][maxn];
int prea[maxn],sufb[maxn];
vector<int> g[maxn];
struct node{
int a,b;
// a 1到j的路径
// b i到j的路径
};
node e[maxn];
void bfs(int id){
dis[id][id]=0;
queue<int> que;
que.push(id);
while(!que.empty()){
int now=que.front();
que.pop();
for(auto x:g[now]){
if(dis[id][x]!=-1) continue;
dis[id][x]=dis[id][now]+1;
que.push(x);
}
}
}
bool cmp(node a,node b){
return a.a-a.b<b.a-b.b;
}
signed main(){
int _;scanf("%d",&_);
while(_--){
scanf("%d",&n);
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1,u,v;i<=n-1;i++){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=-1;
}
bfs(i);
pr[i]=1e9;
}
for(int i=2;i<=n;i++){// 在第i个点
for(int j=1;j<=n;j++){
e[j]={dis[1][j],dis[i][j]};
}
sort(e+1,e+1+n,cmp);
for(int j=1;j<=n;j++){
prea[j]=max(prea[j-1],e[j].a);
}
sufb[n+1]=0;
for(int j=n;j>=1;j--){
sufb[j]=max(sufb[j+1],e[j].b);
}
int pos=0;
for(int j=1;j<=n;j++){
while(pos<n&&e[pos+1].a-e[pos+1].b<j){
pos++;
}
if(pos<n){
pr[j]=min(pr[j],max(prea[pos],sufb[pos+1]+j));
}else{
pr[j]=min(pr[j],prea[n]);
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",pr[i]);
}
printf("\n");
}
return 0;
}