牛客IOI周赛19-提高组 A-基站

基站

前言

终于把这道题补上了

心路

当时画了个这样的图

当时想着能否找出这些红点之间的距离。但似乎不太好实现。换一种思路，因为题目要求最小的d中的最大值。通过图发现点 3 在点 1 与点 6 之间，可以通过3过渡。过渡——对于一个点来说，一定会有离他最近的一个红点，而对于一条边上的两个点，他们连接着红点，也就是说，我可以通过这些边求得红点之间的距离。这些边可以通过跑多源最短路求得。然后枚举这些边的端点，做最小生成树

代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

/*
求出到每个基站最近的基站 
*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=1e5+10,M=5e5+10;

int n,m,tot,k,cnt;
int h[N],nex[M<<1],ver[M<<1],pri[M<<1];
int dis[N],to[N],f[N];

bool vis[N];

struct nkl
{
    int x,y,z;
    bool operator < (const nkl &b)const
    {
        return z<b.z;
    }
}s[M];

struct way
{
    int id;
    bool operator < (const way &b)const
    {
        return dis[id]>dis[b.id];
    }
};

inline void add(int x,int y,int z)
{
    nex[tot]=h[x];
    ver[tot]=y;
    pri[tot]=z;
    h[x]=tot++;
}

inline void spfa()
{
    memset(dis,0x3f,sizeof(dis));
    priority_queue<way>q;
    scanf("%d",&k);
    for (int i=1,x;i<=k;i++)
    {
        scanf("%d",&x);q.push((way){x});
        dis[x]=0;to[x]=x;vis[x]=1;
    }

    while(!q.empty())
    {
        way u=q.top();q.pop();
        vis[u.id]=0;
        for (int i=h[u.id];~i;i=nex[i])
        {
            int j=ver[i];
            if(dis[j]>dis[u.id]+pri[i])
            {
                dis[j]=dis[u.id]+pri[i];
                to[j]=to[u.id];
                if(!vis[j]) vis[j]=1,q.push((way){j});
            }
        }
    }
}

inline int find(int x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for (int i=1,x,y,z;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }

    spfa();

    for (int i=1;i<=n;i++)
        for (int j=h[i];~j;j=nex[j])
        {
            int v=ver[j];
            if(to[v]!=to[i])
            {
                s[++cnt].x=to[i];
                s[cnt].y=to[v];
                s[cnt].z=pri[j]+dis[i]+dis[v];
            }
        }sort(s+1,s+cnt+1);

    for (int i=1;i<=n;i++) f[i]=i;
    int ans=0;
    for (int i=1;i<=cnt;i++)
    {
        int u=find(s[i].x);
        int v=find(s[i].y);
        if(u==v) continue;
        ans=s[i].z;
        f[u]=v;
    }

    printf("%d\n",ans);

    return 0;
}