题意：
给出n点m边的图和长度为m的权值序列，要求分配m条边的权值使得a − > b − > c的最短路权值之和最短。
思路：
求出每个点分别到a , b , c的最少边数，即分别以a , b , c为起点跑最短路。由于权值为1，最短路的本质就是边数。
由于是求权值最小化，先将权值从小到大排序并且求前缀和，记作数组v a l。
如果a − > b和b − > c的路径没有交集，那么答案就是v a l [ s u m ],s u m表示两个路径经过的边的最少数量。
如果两者的路径有交集的话，说明路径是a − > x − > b − > x − >c形式的，枚举中间点x，答案就是v a l [ s u m ] + v a l [ c n t ] ，其中c n t表示x − > b经过的最少边数。
有两个小细节：
权值的范围为1 e 9，边的范围为1 e 5，需要用l o n g l o n g;
枚举x点的时候要判断是否边数> m，这种情况说明会重复走一段路，不会是最优解的，而且也会影响数组大小，容易r e / t l e
代码：
// Problem: E. Weights Distributing // Contest: Codeforces - Codeforces Round #636 (Div. 3) // URL: https://codeforces.com/problemset/problem/1343/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=2e5+7,maxm=1e6+7,mod=1e9+7; ll n,m,a,b,c,val[maxn]; vector<ll>g[maxn]; ll da[maxn],db[maxn],dc[maxn]; void init(){ rep(i,1,n) g[i].clear(); } void bfs(int s,ll dis[]){ rep(i,1,n) dis[i]=1e18; queue<int>q; q.push(s);dis[s]=0; while(!q.empty()){ int t=q.front();q.pop(); for(int tt:g[t]){ if(dis[tt]>dis[t]+1){ dis[tt]=dis[t]+1; q.push(tt); } } } } int main(){ int _=read; while(_--){ n=read,m=read,a=read,b=read,c=read; init(); rep(i,1,m) val[i]=read; sort(val+1,val+1+m); rep(i,1,m) val[i]+=val[i-1]; rep(i,1,m){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } bfs(a,da); bfs(b,db); bfs(c,dc); ll ans=1e18; for(int i=1;i<=n;i++){ //cout<<i<<" "<<da[i]<<" "<<db[i]<<" "<<dc[i]<<endl; if(da[i]+db[i]+dc[i]>m) continue; ans=min(ans,val[db[i]]+val[da[i]+db[i]+dc[i]]); } printf("%lld\n",ans); } return 0; }
