Avito Cool Challenge 2018 D. Maximum Distance (CF 1081D)

题目：Maximum Distance

题意：

给一张图，定义一条路径的长度为这条路径上的边权最大的边的边权。

定义两点间距离为这两点间路径的最小长度。

给出k个特殊节点，求对于每个特殊节点，距离它最远的点到它的距离。

思路：

可以知道，这个距离一定出现在最小生成树上。

所以先跑一遍kruskal，然后取第一个特殊节点dfs求出每个特殊节点到它的距离d[i]，所有节点的最远距离都是 max (d[i])。

代码：

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

#define read(x) scanf(\"%d\",&x)
#define maxn 100000

struct Edge{
	int x,y,z;
	Edge(int xx,int yy,int zz) {
		x=xx,y=yy,z=zz;
	}
	Edge(){}
	bool operator < (const Edge& oth) const {
		return z<oth.z;
	}
	
};

int n,m,K;
int sp[maxn+5];

int fa[maxn+5];
int find(int x) {
	return fa[x]==0?x:fa[x]=find(fa[x]);
}

vector<Edge> e;
vector<Edge> a[maxn+5];

int d[maxn+5];

void dfs(int x,int fa) {
	for(int i=0;i<a[x].size();i++) {
		int y=a[x][i].y;
		if(y==fa) continue;
		d[y]=max(d[x],a[x][i].z);
		dfs(y,x);
	}
}

int main() {
	read(n),read(m),read(K);
	for(int i=1;i<=K;i++) {
		read(sp[i]);
	}
	for(int i=1;i<=m;i++) {
		Edge x;
		read(x.x),read(x.y),read(x.z);
		e.push_back(x);
	}
	
	sort(e.begin(),e.end());
	
	for(int i=0;i<m;i++) {
		int fa1=find(e[i].x),fa2=find(e[i].y);
		if(fa1!=fa2) {
			fa[fa1]=fa2;
			a[e[i].x].push_back(e[i]),a[e[i].y].push_back(Edge(e[i].y,e[i].x,e[i].z));
		}
	}
	
	dfs(sp[1],0);
	
	int max1=0;
	for(int i=1;i<=K;i++) {
		max1=max(max1,d[sp[i]]);
	}
	
	for(int i=1;i<=K;i++) {
		printf(\"%d \",max1);
	}
	
	return 0;
}