E. Long Way Home(最短路径/凸优化)

题目 官方题解

题意

给定n个地点(1,2,3,…,n)以及m条无向的路径，并说明了这m条路径所需要的时间。此外，任何两个地点可以通过航班直接抵达，所需要的距离为他们的编号差的平方和(u-v)*(u-v)。

在最多坐k次飞机的情况下，求每个从城市1，到其他城市的最短路径。

思路 1.不考虑航班路线的最短路径

不考虑航班路线，我们可以用dijkstra算出1号城市到其他城市的最短路径。

2.考虑+1次航班路线的最短路径

利用第一步算出的dist， 再考虑，只走一次航班的场景，此时对于节点u，它的最短路径为 d i s n e w [ u ] = m i n ( d i s o l d [ v ] + ( u − v ) ∗ ( u − v ) ) dis_{new}[u] = min(dis_{old}[v]+(u-v)*(u-v)) disnew​[u]=min(disold​[v]+(u−v)∗(u−v))

如何快速查找对应的v，以来确定 d i s n e w [ u ] dis_{new}[u] disnew​[u]？我们可以用凸优化，它本质上就是利用了斜率。

对于任意两点v1 d i s o l d [ v 2 ] + ( u − v 2 ) ∗ ( u − v 2 ) dis_{old}[v1]+(u-v1)*(u-v1) > dis_{old}[v2]+(u-v2)*(u-v2) disold​[v1]+(u−v1)∗(u−v1)>disold​[v2]+(u−v2)∗(u−v2) 有 ( d i s o l d [ v 2 ] + v 2 ∗ v 2 ) − ( d i s o l d [ v 1 ] + v 1 ∗ v 1 ) < ( 2 ∗ v 2 − 2 ∗ v 1 ) ∗ u (dis_{old}[v2]+v2*v2) - (dis_{old}[v1] + v1*v1) < (2*v2-2*v1)*u (disold​[v2]+v2∗v2)−(disold​[v1]+v1∗v1)v2，且v3更优，有 ( d i s o l d [ v 3 ] + v 3 ∗ v 3 ) − ( d i s o l d [ v 2 ] + v 2 ∗ v 2 ) < ( 2 ∗ v 3 − 2 ∗ v 2 ) ∗ u (dis_{old}[v3]+v3*v3) - (dis_{old}[v2] + v2*v2) < (2*v3-2*v2)*u (disold​[v3]+v3∗v3)−(disold​[v2]+v2∗v2) = k y z u>=k_{xy}>=k_{yz} u>=kxy​>=kyz​时，此时y优于x，z优于y。

当 k x y > = u > = k y z k_{xy}>=u>=k_{yz} kxy​>=u>=kyz​时，此时x优于y，z优于y。

当 k x y > = k y z > u k_{xy}>=k_{yz}>u kxy​>=kyz​>u时，此时x优于y，y优于z。

无论哪种场景，y节点做为中间节点，都不能是最优值。

利用凸优化，我们就可以愉快的去掉那些中间节点，最终维护成一个斜率递增的k数组了。然后，对于每个节点i，我们只要从这个递增的k数组中，找到第一个 m >> k; vector g(n); for (int i = 0; i > u >> v >> w; --u; --v; g[u].push_back({ v, w }); g[v].push_back({ u, w }); } vector dist(n, inf1); dist[0] = 0; dijkstra(g, dist);// 计算不做航班的dist for (int i = 0; i