题解：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)。

代码

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