link：https://codeforces.com/contest/1715/problem/E有\(n\)座城市，城市间有\(m\)条双向道路，通过第\(i\)条道路需要花费\(w_i\)的时间，任意两个城市之间都有航班，乘坐城市\(u\)和\(v\)之间的航班需要花费\((u-v)^2\)的时间。现在请对于任意城市\(i(1\lei\len)\)

这个\(k\)非常小，所以我们考虑全部依次飞这\(k\)次行程。这个飞来飞去是一个平方的形式，我们考虑优化这一形式。首先我们知道从\(u\)飞到\(v\)后就可以这样做：\[dis_u+(u-v)^2\todis_v\]\[dis_u+u^2+v^2-2uv\todis_v\]这里我们可以钦定\(u<v\)，然后斜率

本题并不难。观察一下数据范围\(k\)非常小，那么不难发现我们可以把跳这个操作做\(k\)遍即可。跳操作的式子一看就很斜率优化\((u-v)^2=u^2+v^2-2uv\)直接李超树维护

CF1715E题解题意一个带边权无向图，可以沿着边走，需要边权的花费或从任意点\(u\)飞到\(v\)，需要\((u-v)^2\)的花费。求从点\(1\)到所有\(i\)的最少花费。最多飞\(

套路题。先不考虑额外的边跑一次最短路。然后考虑一下额外的边，单独拿出来转移一次。式子为\(dis_u=min\{olddis_v+(u-v)^2,1\leqv\leqn\}\)。简单的，把凸包建出来，二