CF1343 E. Weights Distributing

E. Weights Distributing

Question

给定由 $n$n个点， $m$m条边构成的无权无向图和 $m$m个权值以及三个点 $a,b,c$a,b,c。问如何分配这 $m$m个权值才能使 $le{n}_{a\to b}+le{n}_{b\to c}$lena→b​+lenb→c​最小

Solution

有两种情况：

1. $a\to x\to b\to x\to c$a→x→b→x→c， $le{n}_{a\to x}+le{n}_{x\to b}+le{n}_{b\to x}+le{n}_{x\to c}$lena→x​+lenx→b​+lenb→x​+lenx→c​
2. $a\to b\to c$a→b→c， $le{n}_{a\to c}$lena→c​

第二种情况是b在a→c的路上，算是1的特例，此时 $le{n}_{b\to x}=0$lenb→x​=0。
最优构造放权值的方法为， $x\to b$x→b这条路上放的权值最小，因为这条路可能要计算两遍。
对每个点进行BFS，求其到其他点的距离，遍历每一个点为x的情况，记录最小值，为了计算路径方便，需要对 $p$p数组排序，然后求其前缀和。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

int n,m,A,B,C;
vector<int> G[N];
int dA[N],dB[N],dC[N];
ll p[N];

void bfs(int s,int *d){
	for(int i=1;i<=n;i++) d[i]=-1;
	queue<int>q;
	q.push(s);d[s]=0;
	while(!q.empty()){
		int t=q.front();q.pop();
		for(auto c:G[t]){
			if(d[c]==-1){
				d[c]=d[t]+1;
				q.push(c);
			}
		}
	}
}

void solve(){
	cin>>n>>m>>A>>B>>C;
	for(int i=1;i<=n;i++) G[i].clear();
	for(int i=1;i<=m;i++) cin>>p[i];
	sort(p+1,p+1+m);
	for(int i=1;i<=m;i++) p[i]+=p[i-1];
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	bfs(A,dA);
	bfs(B,dB);
	bfs(C,dC);
	ll ans=1ll<<60;
	for(int i=1;i<=n;i++) 
		if(dA[i]+dB[i]+dC[i]<=m)
			ans=min(ans,p[dA[i]+dB[i]+dC[i]]+p[dB[i]]);
	cout<<ans<<'\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;cin>>T;
	while(T--){
		solve();
	}
	return 0;
}