考虑线段树分治，每个点只会被加入到 $O(\log n)$ 个分治区间里，每次加入时使用 Floyd 更新当前的 $\operatorname{dis}$ 数组即可。

时间复杂度 $O(n^3 \log n)$。