前言
终于把这道题补上了
心路
当时画了个这样的图
当时想着能否找出这些红点之间的距离。但似乎不太好实现。换一种思路,因为题目要求最小的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; }