Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance
思路
对标记点更新fg,从0开始进行bfs,更新d1为所有点到0的距离
获得到0最远的标记点L,从L开始bfs,更新d2为所有点到L的距离
获得距离L最远的标记点R,从R开始bfs,更新d3为所有点到R的距离
遍历所有点,这个点与标记点的最大距离一定为与L或R的距离
dis[i] = max ( d1[i] , d2[i] )
获得所有点的最小dis即可
#define int long long
#define ld long double
using namespace std;
int t;
queue<int>q;
void op()
{
int n, k;
cin >> n >> k;
vector<bool>fg(n, 0);
for (int i = 0; i < k; i++)
{
int x;
cin >> x;
fg[x - 1] = 1;
}
vector<vector<int>>head(n);
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
head[u-1].push_back(v-1);
head[v-1].push_back(u-1);
}
//bfs,d1为1到点的距离
vector<int>d1(n, -1);
q.push(0);
d1[0] = 0;
while (q.size())
{
int x = q.front();
q.pop();
for (auto y : head[x])
{
if (d1[y] != -1)continue;
d1[y] = d1[x] + 1;
q.push(y);
}
}
//
int L = 0, maxn1 = -1;
for (int i = 0; i < n; i++)
{
if (!fg[i])continue;
if (d1[i] > maxn1)
{
L = i;
maxn1 = d1[i];
}
}
//bfs,d2为点到L的距离
vector<int>d2(n, -1);
q.push(L);
d2[L] = 0;
while (q.size())
{
int x = q.front();
q.pop();
for (auto y : head[x])
{
if (d2[y] != -1)continue;
d2[y] = d2[x] + 1;
q.push(y);
}
}
//
int R = 0, maxn2 = -1;
for (int i = 0; i < n; i++)
{
if (!fg[i])continue;
if (d2[i] > maxn2)
{
maxn2 = d2[i];
R = i;
}
}
//bfs,d3为点到R的距离
vector<int>d3(n, -1);
q.push(R);
d3[R] = 0;
while (q.size())
{
int x = q.front();
q.pop();
for (auto y : head[x])
{
if (d3[y] != -1)continue;
d3[y] = d3[x] + 1;
q.push(y);
}
}
//
vector<int>dis(n, -1);
for (int i = 0; i < n; i++)
{
dis[i] = max(d2[i], d3[i]);
}
int minn = 0x3f3f3f3f;
for(int i = 0; i < n; i++)
{
minn = min(minn, dis[i]);
}
cout << minn << endl;
}
signed main()
{
cin >> t;
while (t--)
{
op();
}
return 0;
}
标签:903,Distance,int,Codeforces,bfs,push,d2,d3,d1
From: https://www.cnblogs.com/ikunhuaji/p/17764690.html