**Hint:**
Ta cần chọn một cạnh $(u, v)$ sao cho **tổng khoảng cách từ tất cả các điểm đặc biệt tới cạnh đó** là nhỏ nhất. Khoảng cách từ một điểm đặc biệt $p_i$ tới cạnh $(u, v)$ được tính là:
$$
\min\big( dist(p_i, u),\ dist(p_i, v) \big)
$$
trong đó `dist(a, b)` là khoảng cách ngắn nhất giữa hai đỉnh.
---
**Các bước thực hiện:**
1. **Đọc dữ liệu và xây dựng đồ thị** dưới dạng danh sách kề.
2. **Tính khoảng cách từ mỗi điểm đặc biệt tới mọi đỉnh**:
* Dùng BFS xuất phát từ từng điểm đặc biệt.
* Lưu kết quả vào mảng `dp[i][v]` = khoảng cách từ điểm đặc biệt thứ `i` đến đỉnh `v`.
3. **Duyệt tất cả các cạnh** $(u, v)$:
* Với mỗi điểm đặc biệt, lấy khoảng cách ngắn nhất tới $u$ hoặc $v$.
* Cộng dồn các khoảng cách lại thành tổng `sum`.
* Bỏ qua cạnh nếu có điểm đặc biệt không thể tới cả hai đầu của cạnh.
4. **Tìm giá trị nhỏ nhất của tổng** và in kết quả.
---
**Độ phức tạp:**
* BFS từ mỗi điểm đặc biệt: $O(k \cdot (n+m))$
* Duyệt tất cả các cạnh để tính tổng: $O(m \cdot k)$
* Tổng thời gian: $O(k \cdot (n+m))$, đủ nhanh với $n, m \le 3000$.
---
Code tham khảo:
```cpp
#include <bits/stdc++.h>
#define ll long long
#define name "TASK"
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
using namespace std;
const int MAXN=3005;
int n, m, k, p[MAXN], d[MAXN];
vector<int> adj[MAXN];
int dp[MAXN][MAXN];
void inp(){
cin>>n>>m>>k;
for(int i=0;i<k;i++){
cin>>p[i];
}
for(int i=0;i<m;i++){
int u, v; cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(d, -1, sizeof(d));
}
void bfs(int u, int idx){
memset(d, -1, sizeof(d));
queue<int> q;
d[u] = 0;
q.push(u);
while(!q.empty()){
int t=q.front(); q.pop();
for(int v:adj[t]){
if(d[v] == -1){
d[v]=d[t]+1;
q.push(v);
}
}
}
for(int v=1; v<=n;v++) dp[idx][v]=d[v];
}
void solve(){
inp();
int res=INT_MAX;
for (int i=0; i<k;i++) {
bfs(p[i], i);
}
for(int u=1;u<=n;u++) {
for(int v : adj[u]) {
if (u < v) {
int sum = 0;
bool c = false;
for(int i=0;i<k;i++){
int du=dp[i][u], dv=dp[i][v];
if (du==-1 && dv==-1) {
c=true;
break;
}
int best=(du == -1 ? dv : (dv == -1 ? du : min(du, dv)));
sum += best;
if(sum >= res) break;
}
if(!c) res=min(res, sum);
}
}
}
cout<<res<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen(name".INP","r")) {
freopen(name ".INP","r",stdin);
freopen(name ".OUT","w",stdout);
}
solve();
cerr << '\n' << "Time collapsed: " << TIME << '\n';
return 0;
}
```