不知道为啥题解都默认认为 $dijkstra$ 可以直接求最长路径，可能是我比较菜吧。

正确性证明：

假设有 $v_0 -> v_i$ 是 $dist 中且 v_i \notin S$（$S$ 为已确定最长路径的点的集合）的最大路径，却不是 $v_0 -> v_i$ 的最长路径，那么一定存在 $v_k \notin S$ 使得 $v_0 -> v_k -> v_i$ 是 $v_0 -> v_i$ 的最长路径。

反证法易证乘法计算的最长路径满足 $largest(v_0 -> v_k -> v_i) = largest(v_0 -> v_k) * largest(v_k -> v_i)$

因为 $v_0 -> v_k$ 必定要从 $S$ 延申边。不妨认为 $v_k$ 是已记录到 $dist$ 中的点。

因为汇率 $0 < w <= 1$ ，有 $largest(v_0 -> v_k), largest(v_k -> v_i) >= 1$ ，如果为 1 ，不影响最长路径；如果不为 1 一定有 $largest(v_0 -> v_k) = dist(v_0 -> v_k) > dist(v_0 -> v_k -> v->v_i)$，与条件矛盾。