对于本题，dijkstra 算法只需要改动计算路径权值的很小一部分让我感觉挺意外的qwq

即，dijkstra 的其它部分不变，只是在拓展结点时的距离计算由：

dist[u]+w(u, v)

改为：

max(dist[u], w(u, v)))

（变量名感性理解下X）

题中对一个路径 $p$ 的权值的定义是 $w(p)=\max\limits_{(u, v)\in p}(w(u, v))$

虽然该定义下的 “最短路径” 不具有最优子结构$^1$，但随着路径边数的增加，$w(p)$ 是不减的；且 dijkstra 其它部分也未被改动或影响（对最短路估计不增等等性质仍然适用）。于是原来对 dijkstra 算法的证明仍然适用（可能会特指算法导论上的证明qaq，其它证明我还没怎么看过）

脚注

[1]: 即若有 $w(p(s, t))$ 最小，对于 $(u, v)\in p(s, t)$，不一定有 $w(p(s, u))$ 或 $w(p(v, t))$ 最小。这是因为路径权值仅依赖于边权最大的边，只要这条边不变，路径的其它部分可以在不改变路径最大边的前提下任意改动