题意理解
NNN 个点 MMM 条边的无向图，求从 111 到 NNN 的最短路。可以选择一条边使其长度加倍，问最大能使最短路增加多少。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
关键观察：
如果加倍的边不在原最短路上，那么最短路不会改变（原路径仍然可用）。
因此只需枚举最短路上的每条边，将其加倍后重新计算最短路。
算法流程：
1. 先跑一次 Dijkstra，求出原始最短路，并记录路径
2. 枚举最短路上的每条边 (u,v,w)(u, v, w)(u,v,w)，将其权值临时改为 2w2w2w
3. 重新跑 Dijkstra，计算新的最短路
4. 增量 = 新最短路 - 原最短路，取所有增量的最大值
复杂度分析：
最短路上最多 N−1N-1N−1 条边，每次 Dijkstra 为 O((N+M)logN)O((N+M) log N)O((N+M)logN)，总复杂度 O(N⋅(N+M)⋅logN)O(N \cdot (N+M) \cdot log N)O(N⋅(N+M)⋅logN)，可以通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
