题解：P15818 [JOI 2015 Final] JOI 公园 / JOI Park

daguotuan · 2026-04-25 13:38:54 · 题解

题目大意：

给我们一个连通无向图和 C，节点编号为 1 到 n。选一个非负数 X，把距离 1 号点小于等于 X 的点与 1 号点连上地下通道（包括 1 号点本身），将所有已被地下通道连接的点对之间的边全部拆掉，总代价为 C \times X 与剩下所有边权的和，选出 X 要求总代价最小，输出其方法总代价。

思路：

从 1 号点开始跑 Dijkstra，排序距离，从小枚举 X，每次标记一个已被地下通道连接的点，枚举其边，若连接的点也被标记，则拆掉此边，然后算总代价就简单了。

Code 和 AC 记录：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back

struct test
{
    int v;
    int w;
};

struct node
{
    int u;
    int d;
};

struct cmp
{
    bool operator()(const node &a,const node &b)
    {
        return a.d>b.d;
    }
};

struct dd
{
    int d;
    int idx;
};

int n,m,c;
vector<vector<test>> vmp(100100);
dd dis[100100]={};
bool b[100100]={};

inline void init()
{
    for(int i=1;i<=n;i++)
    {
        dis[i].idx=i;
    }
}

inline void dijk(int start)
{
    for(int i=1;i<=n+5;i++) dis[i].d=1e18;
    dis[start].d=0;
    priority_queue<node,vector<node>,cmp> pq; 
    pq.push({start,0});
    while(!pq.empty())
    {
        auto[u,d]=pq.top();
        pq.pop();
        if(d>dis[u].d)
        {
            continue;
        }
        for(auto[v,w] : vmp[u])
        {
            int nd=d+w;
            if(nd<dis[v].d)
            {
                dis[v].d=nd;
                pq.push({v,nd});
            }
        }
    }
}

signed main()
{
    cin>>n>>m>>c;
    int sum=0;
    init();
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        sum+=w;
        vmp[u].pb({v,w});
        vmp[v].pb({u,w});
    }
    dijk(1);
    sort(dis+1,dis+1+n,[](dd a,dd b)
    {
        return a.d<b.d;
    });
    int ans=1e18;
    for(int i=1;i<=n;i++)
    {
        int x=dis[i].d;
        int u=dis[i].idx;
        b[u]=1;
        for(auto[v,w] : vmp[u])
        {
            if(!b[v]) continue;
            sum-=w;
        }
        ans=min(ans,sum+x*c);
    }
    cout<<ans;
}

AC 记录。