[CCC 2023 S4] 最低成本道路 题解

1.题目

有$n$个点，$m$条边，每条边有长度 $l$ ，权值 $c$ ，组成一个原图

你需要构造一个新图，满足以下条件：

• 仍然有$n$个点，且联通。

• 新图上的边都是原图中的边

• 对于任意一个点对 $(u,v)$，满足新图上从 $u$ 到 $v$ 的路径长度（每条边的 $l$ 之和）不大于原图上从 $u$ 到 $v$ 的路径长度

定义这个新图的代价：所有边的 $c$ 之和

你需要最小化这个代价

2.思路

考虑贪心

首先，题目中先要求了：

对于任意一个点对 $(u,v)$，满足新图上从 $u$ 到 $v$ 的路径长度（每条边的 $l$ 之和）不大于原图上从 $u$ 到 $v$ 的路径长度

这是优先级最高的条件

在满足这个条件后，你需要：

让新图代价尽量小

这时候，我们就可以设计出贪心思路：

• 首先，将所有边按 $l$ 排序

• 然后，当 $l$ 相等时，按 $c$ 排序。

• 最后，在新图中加入边时，跑最短路，判断加入这条边会不会让某些路径的长度缩短 ，如果会，则加入这条边

为什么？

排序应该很好理解吧，因为优先级就是这样的

但是加入边时，为什么是这样呢？

如果加入这条边会让某些路径的长度缩短

则说明当前构造的这个新图不满足 条件：

对于任意一个点对 $(u,v)$，满足新图上从 $u$ 到 $v$ 的路径长度（每条边的 $l$ 之和）不大于原图上从 $u$ 到 $v$ 的路径长度

好吧，这挺显然的

但是这里还要注意一下：

当加入边 $(u,v)$ 时，

你不需要遍历所有点对，判断路径长度是否会变短

你只需要判断从 $u$ 到 $v$ 的路径会不会变短

这也很好理解

如果加入的边不会让这条路径变短

那么其他的路径也不会经过这条边（它可以经过更优的另外一条路径 ）

所以，总的下来，视 $n,m$ 同阶，整个复杂度大概是 $O(n^2\log{n})$

能过

3.Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,dis[2010],vis[2010];
vector<pair<int,int> >e[200010];
void check(){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	dis[s]=0;
	q.push({dis[s],s});
	while(q.size()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:e[u]){
			if(dis[u]+w<=dis[v]){
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
}//跑DJ
struct no{
	int u,v,l,w;
}g[200010];
main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,l,w;
		cin>>u>>v>>l>>w;
		g[i]={u,v,l,w};
	}
	sort(1+g,1+g+m,[&](no x,no y){
		if(x.l==y.l)return x.w<y.w;
		return x.l<y.l;
	});int ans=0;
	for(int i=1;i<=m;i++){
		int u=g[i].u,v=g[i].v,l=g[i].l,w=g[i].w;
		s=u;
		check();
		if(dis[v]>l)e[u].push_back({v,l}),e[v].push_back({u,l}),ans+=w;//判断是否会让路径变短
	}
	cout<<ans;
	return 0;
}