本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 16:10:35

定义 $dis(i,j)$ 表示从 $i$ 走到 $j$ 的最少边数。

假设 $a \sim b$ 与 $b \sim c$ 的路径没有重合的话，那么只需要 $p$ 中最小的 $dis(a,b)+dis(b,c)$ 个数值，将它们赋到 $a \sim b$ 和 $b \sim c$ 的路径上就可以了。

但是现在的问题就在于路径重合的问题，如果还按照刚才的算法会把答案算大，甚至找到不存在的路径（即 $dis(a,b)+dis(b,c) \gt m$ 的清空）。

考虑枚举重合信息。

枚举 $md$ 作为 $b$ 到 $c$ 的路径上最后一个与 $a \sim b$ 路径重合的节点。

那么，此时路径将分为三个部分：

• $a \sim md$ 的路径，路径上的边计入一次答案。
• $md \sim b$ 的路径，路径上的边计入两次答案。
• $md \sim c$ 的路径，路径上的边计入一次答案。

此时按照最优方式，上述三段路径都按照最短路计算就可以了，即路径长度分别为 $dis(a,md),dis(md,b),dis(md,c)$。

然后，优先把 $p$ 中较小的数值分配给第二部分的路径，然后再分配一，三部分的路径就行了。

尽管有可能因此不再满足路径重合的一些条件，但是这仍然是对的，由于以下两点：

• 对于最优的路径，一定会被上述过程枚举到。
• 上述枚举的路径一定是一条合法的路径。

对于最短路的计算，bfs 预处理 $a,c$ 到其他所有点的最小边数就可以了。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=2e5+5;
int n,m,a,b,c;
ll p[maxn],pre[maxn];
ll w(int l,int r){
    return pre[r]-pre[l-1];
}
vi g[maxn];
int disa[maxn],disb[maxn],disc[maxn];
void bfs(int s,int* dis){
    FOR(i,1,n)dis[i]=1e9;
    queue<int> q;
    q.push(s);
    dis[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int& v:g[u]){
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
}
void clear(){
    FOR(i,1,n){
        g[i].clear();
    }
}
void solve(int id_of_test){
	read(n);
    read(m);
    read(a);
    read(b);
    read(c);
    FOR(i,1,m){
        read(p[i]);
    }
    sort(p+1,p+m+1);
    FOR(i,1,m){
        pre[i]=pre[i-1]+p[i];
    }
    FOR(i,1,m){
        int u,v;
        read(u);
        read(v);
        g[u].eb(v);
        g[v].eb(u);
    }
    bfs(a,disa);
    bfs(b,disb);
    bfs(c,disc);
    ll ans=1e18;
    FOR(mid,1,n){
        \/\/ a-->b
        \/\/ b-->c
        \/\/ 上述路径共同都要到达 mid
        int len=disb[mid];
        if(len+disa[mid]+disc[mid]>m)continue;
        ll res=pre[len]*2;
        res+=w(len+1,len+disa[mid]+disc[mid]);
    \/\/    printf("mid = %d res = %lld\n",mid,res);
        ckmn(ans,res);
    }
    printf("%lld\n",ans);
    clear();
}
int main()
{
	int T;
	read(T);
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}
\/*
1. 对题意的理解能否和样例对的上？  
2. 每一步操作，能否和自己的想法对应上？  
3. 每一步操作的正确性是否有保证？  
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？  
*\/