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;
}
- Codeforces Distance Minimum Maximum Roundcodeforces distance minimum maximum distance minimum maximum 1881f 题解distance minimum maximum codeforces distance social round codeforces distance round axis codeforces strength maximum round codeforces minimum hossam round codeforces distance matching 1396e codeforces minimize distance 1591c codeforces distance 1446f line