根据 dalao 的建议和洛谷的格式规范优化了下排版

dijkstra 算法正确性证明：

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

反证法易证乘法计算的最长路径满足 $\operatorname{largest(v_0 \to v_k \to v_i)} = \operatorname{largest(v_0 \to v_k)} \times \operatorname{largest(v_k \to v_i)}$

因为 $v_0 \to v_k$ 必定要从 $S$ 延申边。不妨认为 $v_k$ 是已记录到 $\operatorname{dist}$ 中的点。

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

因此最长路径一定来自于其他最长路径且 $\operatorname{dist}$ 中最长路径就是全局最长路径。