【題解】Codeforces 1343E. Weights Distributing

#include <bits/stdc++.h>
using namespace std;

int t, n, m, a, b, c, cost[200005], da[200005], db[200005], dc[200005];
long long pre[200005];
vector <int> v[200005];

void bfs(int s, int (&dis)[200005]){
    queue <int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty()){
        int now = q.front();
        q.pop();
        for (auto i:v[now]){
            if (dis[i] != -1) continue;
            dis[i] = dis[now]+1;
            q.push(i);
        }
    }
}

int main(){
    cin >> t;
    while (t--){
        cin >> n >> m >> a >> b >> c;
        for (int i = 1; i <= n; i++){
            da[i] = db[i] = dc[i] = -1;
            v[i].clear();
        }
        for (int i = 1; i <= m; i++){
            cin >> cost[i];
        }
        sort(cost+1, cost+m+1);
        for (int i = 1; i <= m; i++){
            pre[i] = pre[i-1]+cost[i];
        }
        for (int i = 0, x, y; i < m; i++){
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        bfs(a, da);
        bfs(b, db);
        bfs(c, dc);
        long long ans = 1e18;
        if (da[b]+dc[b] <= m) ans = min(ans, pre[da[b]+dc[b]]);
        for (int i = 1; i <= n; i++){
            int tmp = da[i]+dc[i]+db[i];
            if (tmp > m) continue;
            ans = min(ans, pre[db[i]]+pre[tmp]);
        }
        cout << ans << "\n";
    }
}