这道题真的是看上去太哄人了....
首先我们把问题简化,从简单到一般,假设只有两个特殊点的话(x,y),那么考虑其中一个点x的答案是什么?那么就是x到y的距离是x的答案(毕竟没有其他的特殊点了...)。那么考虑x到y的距离是什么?显然的是x到y有很多条路径,每条路径中的最大边权就是这条路径的价值。那么距离就是所有路径的最小值。(习惯:看到最大值最小就想到二分...)。换句话说,假使答案是这个距离ans的话,那么从x到y,一定有一条路径所有的边权<=ans,且其他路径中的最大值都大于这个ans.考虑这个是什么情况,对!连通性,也就是说这个ans是最小的使得x到y联通的边权的边界。考虑更多点的情况,假设有很多点,我们仍考虑点x的答案,即对其他点y,z,a,b,...的距离的最大值。我们可以像刚才一样,假设答案为ans,再具体的代入,那么就是x到其他点y,z,a,b,...有很多的路径,其中点x与某个点的最小联通边权的边界为ans,由于这个ans是所有其他点的距离取max,那么点x到其他所有点的最小联通边权<=ans,换句话说,点x只靠边权<=ans的边,一定能与其他的点联通。那么这个ans就显而易见了,ans的定义就是点x与其他所有点联通的最小边权。同时注意到点x与其他所有点联通,意味着这所有的特殊点是相互联通的。而且我们在上述求解时并没有用到关于点x的具体的信息,说明,这对于所有的点都适用,换句话说,所有点的答案都是一样的。那么这就好做了,我们先二分,后判断连通性即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,m,k,x[N],f[N];
struct bian{int x,y,v;}a[N];
inline bool cmp(bian x,bian y) {return x.v<y.v;}
inline int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
inline bool check(int mid)
{
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=mid;++i)
{
int t1=getf(a[i].x),t2=getf(a[i].y);
if(t1!=t2) f[t1]=t2;
}
int o=getf(x[1]);
for(int i=2;i<=k;++i) if(getf(x[i])!=o) return false;
return true;
}
int main()
{
freopen("1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;++i) scanf("%d",&x[i]);
for(int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
sort(a+1,a+m+1,cmp);
int l=1,r=m;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
for(int i=1;i<=k;++i) printf("%d ",a[l].v);
return 0;
}