题解：P9327 [CCC 2023 S4] Minimum Cost Roads

分析

正向删边不好考虑，那么考虑逆向加边，按长度为第一关键字，费用为第二关键字排序，对于新加入的一条边，其长度为

l

，连接的两点为

u

，

v

，设

u

，

v

间最短路长度为

\operatorname{dis}(u,v)

，若

l \ge \operatorname{dis}(u,v)

，加入后结果显然更劣，因为其余点的最短路径显然不回经过此点。若

l < \operatorname{dis}(u,v)

，加入后会使一些节点之间的最短路变短，必须加入。

时间复杂度为

O(m^2 \log m)

。

代码

CPP

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#define int long long
#define N 2005
#define inf 1e9+5
#define PII pair<int,int>
using namespace std;
inline void read(int &x){
	int f=1; x=0; 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();
	}
	x*=f;
}
inline void write(int x){
	if(x<0)
		putchar('-'),x=-x;
	if(x>=10)
		write(x/10);
	putchar(x%10+'0');
}
int n,m;
vector<PII> e[N];
int dis[N];
bool vis[N];
struct Road{
	int u,v,l,c;
}a[N];
int ans;
bool cmp(Road x,Road y){
	if(x.l==y.l)
		return x.c<y.c;
	return x.l<y.l;
}
int Dijkstra(int s,int ed){
	priority_queue<PII> q;
	for(int i=1;i<=n;i++)
		dis[i]=inf,vis[i]=false;
	dis[s]=0;
	q.push({0,s});
	while(!q.empty()){
		PII tmp=q.top(); q.pop();
		int u=tmp.second;
		if(vis[u])
			continue;
		vis[u]=true;
		if(u==ed)
			return dis[u];
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].first,w=e[u][i].second;
			if(dis[u]+w<dis[v]&&!vis[v]){
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
	return inf;
}
signed main(){
	read(n); read(m);
	for(int i=1;i<=m;i++)
		read(a[i].u),read(a[i].v),read(a[i].l),read(a[i].c);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		int u=a[i].u,v=a[i].v,l=a[i].l,c=a[i].c;
		if(l<Dijkstra(u,v))
			ans+=c,e[u].push_back({v,l}),e[v].push_back({u,l});
	}
	write(ans);
	return 0;
}

题解：P9327 [CCC 2023 S4] Minimum Cost Roads

文章操作

分析

代码

相关推荐

评论

题解：P9327 [CCC 2023 S4] Minimum Cost Roads