还是比较牛的。
首先枚举一条边，钦定其中一个点，枚举这个点的出边作为 Q，然后再跑一个最小环就是结果了。
注意到此时是 \(O(n^4)\) 的，我们利用线段树分治解决 Floyd 中挖掉一个点求最短路的问题。
同样将枚举点换成边，Floyd 换成 dijkstra，然后注意到 Q 的边只可能是一个点出边的前 \(3\) 小，枚举一下，注意要判断一下第一条边的颜色，即可做到 \(O(n^3)\)。因为 dijkstra 不用堆优化反而更优。
还是比较牛的。
首先枚举一条边，钦定其中一个点，枚举这个点的出边作为 Q，然后再跑一个最小环就是结果了。
注意到此时是 \(O(n^4)\) 的，我们利用线段树分治解决 Floyd 中挖掉一个点求最短路的问题。
同样将枚举点换成边，Floyd 换成 dijkstra，然后注意到 Q 的边只可能是一个点出边的前 \(3\) 小，枚举一下，注意要判断一下第一条边的颜色，即可做到 \(O(n^3)\)。因为 dijkstra 不用堆优化反而更优。