瓶颈路

昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。

由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。

今天查看题解，发现有几个重要的，从未考虑过的trick：

1. 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
2. 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。

（更多…）