最便宜的车票题解

题意是求最短路，可以选择一个点使得与这个点相连的所有边边权变为1。
假设我们选择的点是x，经过x的最短路是：
1—>......—>a—>x—>b—>......—>n
答案就是min{dis(1,a)+dis(b,n)+2}，这里a和b要同时和一个点相连。
我们可以用最短路算法求出1和n到其他所有点的最短路，dij和spfa都是可以的。
然后再依次枚举点就好，复杂度总的来说，用dij的话，是O(nlogn+m)的。