Дано связный невзвешенный граф с N вершинами N-1 ребром. И также подграф етого графа P. Найти вершину от которой расстояние до каждой вершины подграфа P будёт минимальна и вывести само расстояние.
Буду рад любой идеи к решению, а сейчас немного про ограничения:
TIME : 2 сек
MEMORY : 256 МБ
N, K <= 10^5, где N количество вершин графа, а K количество вершин подграфа P
Так же наведу пример для наглядности:
N K
| |
8 4
Далее задано N - 1 ребер:
1 2
1 3
1 4
4 6
4 5
5 7
5 8
Далее K чисел через пробел, вершины подграфа P:
2 5 6 7
Ответ:
6
Моя попытка, которая идёт на лимит времени:
#include <bits/stdc++.h>
using namespace std;
int n;
int BFS(vector<vector<int>> graph, int from, int to)
{
vector <bool> mark(1 + n, true);
vector <int> dist(1 + n, 0);
queue <int> Q;
Q.push(from);
mark[from] = false;
while (!Q.empty())
{
int v = Q.front();
Q.pop();
for (int i = 0; i < graph[v].size(); ++i)
{
int vert = graph[v][i];
if (mark[vert])
{
mark[vert] = false;
dist[vert] = 1 + dist[v];
Q.push(vert);
}
}
}
return dist[to];
}
int main()
{
int m;
cin >> n >> m;
vector <vector<int>> graph(1 + n);
for (int i = 0; i < (n - 1); ++i)
{
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector <int> P(m);
for (int i = 0; i < m; ++i)
{
cin >> P[i];
}
int ans = INT_MAX;
for (int from = 1; from <= n; from++)
{
int cur = 0;
for (auto to : P)
{
int dist = BFS(graph, from, to);
cur += dist;
}
ans = min(ans, cur);
}
cout << ans << endl;
return 0;
}