最短路径

一个粗略的想法：

先做两次Dijkstra算法，求出点1到每个点的最短路径长度f[i]以及点N到每个点的最短路径长度g[i]，并求出1到N的最短路径长度d

然后，对于图中的每条边(u,v)，当其距离减半后，有以下几种可能
1、点1到点N的最短路径不经过现在的(u,v)，此时1到N的最短距离仍为d
2、新的点1到点N的最短路径是从点1走最短路径到达点u，经过边(u,v)，再从v走最短路径到达N，此时1到N的最短距离是d'=f[u]+l[u,v]/2+g[v]，且必然有d'<d
3、新的点1到点N的最短路径是从点1走最短路径到达点v，经过边(v,u)，再从u走最短路径到达N，此时1到N的最短距离是d'=f[v]+l[u,v]/2+g[u]，且必然有d'<d
也就是说，当(u,v)长度减半后，只有新的1到N的最短路径只可能是这三条路径中最短的
1、原先的最短路径
2、点1->...->点u->点v->...->点N
3、点1->...->点v->点u->...->点N

因此，新的最短路径长度就是d 、 f[u]+l[u][v]/2+g[v] 、 f[v]+l[u][v]/2+g[u]中的最小值
这样就求出了当某一条边(u,v)长度减半时，新的最短路径长度
循环考虑每一条边，就可以求出最短的新最短路径，这样也就求出了最短距离减少的最大值