思路解析
题意：邮递员从节点 1 出发，分别送东西到节点 2, 3, ..., n，每送完一件必须回到节点 1。求总最短时间。
关键公式：
答案=∑i=2n(dis(1→i)+dis(i→1))\text{答案} = \sum_{i=2}^{n} \left( dis(1 \to i) + dis(i \to 1) \right) 答案=i=2∑n (dis(1→i)+dis(i→1))
去程很简单：从节点 1 跑一次 Dijkstra，得到 1 到每个点的最短路。
返程的难点：要求每个点 iii 到节点 1 的最短路，如果对每个点都跑一次 Dijkstra，需要 nnn 次，太慢。
反向图技巧：把所有边的方向反过来，在反向图上从节点 1 跑一次 Dijkstra，得到的 dis2[i]dis2[i]dis2[i] 就等于原图中从 iii 到 1 的最短路。
> 原图中 i→⋯→1i \to \cdots \to 1i→⋯→1 的一条路径，反向后变成 1→⋯→i1 \to \cdots \to i1→⋯→i，长度不变。
所以总共只需要 2 次 Dijkstra。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
完整代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
为什么反向图有效？
原图路径 反向图路径 长度 3→65→24→813 \xrightarrow{6} 5 \xrightarrow{2} 4 \xrightarrow{8} 136 52 48 1 1→84→25→631 \xrightarrow{8} 4 \xrightarrow{2} 5 \xrightarrow{6} 318 42 56 3 都是 16
每条边 u→wvu \xrightarrow{w} vuw v 反向变成 v→wuv \xrightarrow{w} uvw u，路径上每条边都反向，总长度不变。所以原图中 i→1i \to 1i→1 的最短路 = 反向图中 1→i1 \to i1→i 的最短路。
