当前位置：首页 > news >正文

Codeforces Round #636 (Div. 3) E. Weights Distributing（bfs求无向无权图最短路径）

news 来源：原创 2024/4/27 22:08:42

题目链接

在这里插入图片描述
1.题目大意：给出一个无向无权图和三个顶点 $a, b, c$ ，要求先从 $a$ 走到 $b$ 再从 $b$ 走到 $c$ 。现在可以给每一条边分配一个权重，问如何分配使得 $a - > b - > c$ 的权值和最小

2.第一眼的想法：我们可以先从 $a$ 开始直接走到 $b$ ，记录下来它的最短路径，建立一个边 $(p a i r)$ 对应的 $m a p$ ，更新无向图路径的无向边；同理 $b - > c$ ，那么最后得到的是每条无向边出现的频率，然后肯定是出现次数最多的分配最小的权值，详见传送门。但是没想到的是 $b f s$ 只保证了走的最短路径，但是路径可能有多条，最好的是走两种路径尽量重合多的边，但是这没办法控制，因此此方法行不通

3.正解：

$a - > b - > c$ 的路径，假设可以由边 $x$ 作中转点，那么如果路径重复的话就是 $a - > x - > b - > x - > c$ （路径不重复其实 $x$ 就是 $b$ 点），如下图所示
$b f s$ 分别求出 $a, b, c$ 到其他任意点的最短路径长度
预处理走 $k$ 条不重复边需要的最小权值，也就是先给权值数组排序再取第 $k$ 前缀和，设前缀和数组为 $s$
枚举每个可能的 $x$ 点，那么 $a - > b - > c$ 的路径的种数为== $a$ 到 $x$ 的距离+ $b$ 到 $x$ 的距离+ $c$ 到 $x$ 的距离==。而最小的权值应先分配给 $b - > x$ 的这段路径，因为 $b - > x$ 要走两遍，而 $a - > x$ 和 $c - > x$ 只需要走一遍。因此，最小值即为 $s [a$ 到 $x$ 的距离+ $b$ 到 $x$ 的距离+ $c$ 到 $x$ 的距离 $]$ + $s [b$ 到 $x$ 的距离 $]$

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

vector<int> G[maxn];
ll value[maxn];
bool vis[maxn];
int d1[maxn],d2[maxn],d3[maxn];  //分别表示a,b,c到各点的距离

void bfs(int u,int *dis){
	memset(vis,0,sizeof vis);
	queue<int> q;
	vis[u]=1;
	dis[u]=0;
	q.push(u);
	while(!q.empty()){
		int v=q.front(); q.pop();
		for(auto i : G[v]){
			if(!vis[i]){
                vis[i]=1;
                dis[i]=dis[v]+1;
                q.push(i);
			}
		}
	}
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t,n,m,a,b,c,x,y;
	cin>>t;
	while(t--){
		cin>>n>>m>>a>>b>>c;
		for(int i=1;i<=m;i++) cin>>value[i];
        for(int i=0;i<=n;i++) G[i].clear();
        for(int i=1;i<=m;i++){
			cin>>x>>y;
			G[x].push_back(y);
			G[y].push_back(x);
		}
		bfs(a,d1);
		bfs(b,d2);
		bfs(c,d3);
        sort(value+1,value+1+m);
		for(int i=1;i<=m;i++)
            value[i]+=value[i-1];
		ll ans=INF;
		for(int i=1;i<=n;i++){
			if(d1[i]+d2[i]+d3[i]<=m)  //注意这里的特判
                ans=min(ans,value[d1[i]+d2[i]+d3[i]]+value[d2[i]]);
		}
		cout<<ans<<endl;
	}
    return 0;
}