「JOISC 2014 Day2」水壶

# 「JOISC 2014 Day2」水壶 ------ ### 子任务$1$： 暴力求出每两个点之间的最小代价， 用 $Floyd$ 求出每两个点之间的最小代价。 ------- ### $100$pts: 理想情况下，如果我们知道每两个点之间的最小距离， 能在$log$的时间里面解决吗？ 显然不能。 所以肯定不是求每两个点之间的最小距离。 ------------ 这题有一个特殊的地方， 求的是**边的最大值** 那我们希望用最短的边构成一个连通图， 显然想到**构造最小生成树**啊。 所以$bfs$一遍，把所有的点塞入队列 每次到达一个点的时候标记，并记录距离和这个点的$id$ 造了最小生成树（注意可能是森林）之后， $dfs$ 之后倍增求解即可。