最短缩减路径
给定一张无向图，你可以让任意一条边的权值减半，求起点到终点的最短路径。
点数 \(\le 500\)；边数 \(\le 50000\)；\(1\le\) 边权 \(\le 500000\)，且均为偶数。
本题有两种思路：
- 分层图，就只有一条边，只需要分两层，是比较简单的模型应用。
- 计算从起点、终点到其他所有点的距离，然后枚举中间的任意一条边（方向不同视作不同的边），计算三部分：起点到边一端、这条边的权值减半、边另一端到终点，由于是无向图，所以从终点到其他所有点的距离等价于从其他所有点到终点的距离，把三部分相加即可。