D. Ela and the Wiring Wizard（最短路径/floyd）

题目 参考

题意

给定一个带权无向图，n个点，m条带权无向边。

要从点1走到点n。

走之前，可以执行以下操作 对于连接点u,v，边权为w的边，可以将它从点u移除，并连接到任意一个与v相邻的点（点v也可以与自己相连）。但需要花费的时间为w单位。

可以执行以上操作任意次。

问，执行了上述若干次操作后，从点1走到点n，需要的最短时间是多少（包括修改边时花费的时间）。

思路 定理1：点1到点n的最短路径，经过的边，边权一定相同。

反证法：如果点1到点n的最短路径，存在两条相邻的边，边权不同，w1，w2，不失一般性，我们假设w1