AT_joi2015ho_c 题解

ikunTLE · 2026-07-21 18:09:16 · 题解

思路

首先跑一遍最短路，预处理出 1 号点到其他点的距离。同时预处理所有边权的和 S。再将到每个点的距离从小到大排序，排序后按照距离枚举 X。

枚举到当前点 u 时，遍历 u 的所有边，如果连接的点 v 已经被遍历过，那么就可以删除这条边，将 S 减去当前点的边权。此时总成本为 CX+S，答案取最小的成本即可。

由于每一条边只会被遍历 2 遍，所以时间复杂度来自最短路，时间复杂度为 \mathcal O((N+M)\log N)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,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();return x*f;}
const int N=1e5+10;
struct ver{
    int id,dis;
    friend bool operator<(const ver cmp1,const ver cmp2){
        if(cmp1.dis!=cmp2.dis)
            return cmp1.dis<cmp2.dis;
        return cmp1.id<cmp2.id;
    }
}f[N];
bool vis[N],flag[N];
struct edge{
    int to,w;
};vector<edge>vc[N];
struct node{
    int u,dis;
    friend bool operator>(const node cmp1,const node cmp2){
        return cmp1.dis>cmp2.dis;
    }
};priority_queue<node,vector<node>,greater<node>>pq;
void dijkstra(){
    memset(f,0x3f,sizeof(f));
    f[1].dis=0,pq.push({1,0});
    while(!pq.empty()){
        auto[u,dis]=pq.top();pq.pop();
        if(vis[u])
            continue;
        vis[u]=true;
        for(auto[v,w]:vc[u]){
            int temp=dis+w;
            if(temp<f[v].dis){
                f[v].dis=temp;
                pq.push({v,temp});
            }
        }
    }
    return;
}
signed main(){
    int n=read(),m=read(),c=read(),sum=0;
    while(m--){
        int u=read(),v=read(),w=read();
        vc[u].push_back({v,w});
        vc[v].push_back({u,w});
        sum+=w;
    }
    dijkstra();
    for(int i=1;i<=n;++i)
        f[i].id=i;
    sort(f+1,f+n+1);
    int ans=LLONG_MAX;
    for(int i=1;i<=n;++i){
        auto[u,x]=f[i];
        for(auto[v,w]:vc[u])
            if(flag[v])
                sum-=w;
        flag[u]=true;
        ans=min(ans,c*x+sum);
    }
    printf("%lld\n",ans);
    return 0;
}