题解：AT_abc287_h [ABC287Ex] Directed Graph and Query

原题Link

版，不知道为什么评绿。

题意

其实就是一个类全源最短路，求 $s_x$ 到 $t_x$ 的最小值。

Solution

考虑 Floyd。

众所周知，Floyd 要从大到小枚举每一个节点转折点的 $k$，而在这个过程中，如果有一组询问的两个端点恰好连通，则说明最大值为当前转折点。

发现是一个传递闭包。

可以先把每组查询存下来，在在跑 Floyd 时再去更新答案。

发现 $O(n^3)$ 跑不过去，故用 bitset 优化到 $O(\frac{n^3}{w})$，在 $4.5s$ 的时限下可以通过。