[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;
}