这题让我们对边权进行赋值，首先肯定想到，假如不考虑边权，那么我们也是要求a-b，b-c的路径最短是多少，因为路径少意味着权值少
这里有两种情况，一种是这两者之间存在某个点x，使得部分路径重复，一种是不存在
其实这两个是一种情况，第二种情况的b就是x。这样我们发现重复的路径要走两边，肯定是将他赋值到最小，而其他的，就贪心的从剩下小的里面拿
因此现在不考虑权值，那么直接求三遍bfs就能求出三个点到其他各点最少经过的路径，接着枚举中间点x，就能求出答案
这里还要注意的是，因为我们是暴力枚举，所以可能存在三条路径加起来大于总边数的情况，这种情况直接continue，因为显然不会选。
#include <cstring> #include <iostream> #include <algorithm> #include <map> #include<queue> using namespace std; const int N=4e5+10; int n,m,a,b,c; int h[N],ne[N],e[N],idx; int da[200010],db[200010],dc[200010]; int w[N]; long long s[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void init(){ memset(da,0x3f,sizeof da); memset(db,0x3f,sizeof db); memset(dc,0x3f,sizeof dc); memset(h,-1,sizeof h); } void bfs(int dis[],int x){ queue<int> q; dis[x]=0; q.push(x); while(q.size()){ int t=q.front(); q.pop(); int i; for(i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(dis[j]>dis[t]+1){ dis[j]=dis[t]+1; q.push(j); } } } } int main(){ int t; cin>>t; while(t--){ init(); int i; cin>>n>>m>>a>>b>>c; for(i=1;i<=m;i++){ scanf("%d",&w[i]); } sort(w+1,w+1+m); for(i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } bfs(da,a); bfs(db,b); bfs(dc,c); for(i=1;i<=m;i++){ s[i]=s[i-1]+w[i]; } long long ans=1e18; for(i=1;i<=n;i++){ if(da[i]+db[i]+dc[i]>m) continue; ans=min(ans,1ll*s[db[i]]+s[db[i]+da[i]+dc[i]]); } cout<<ans<<endl; } }