思路

付费规则把相邻两条道路绑定在一起。为记录尚未配对的第一条道路，可以把状态扩展为“当前城市”和“上一条未结算道路的权值”。权值只在 $1$ 到 $50$ 之间，因此每个城市只需常数个扩展状态。

将一对权值为 $x,y$ 的道路费用拆成 $x^2+2xy+y^2$。经过第一条道路时先加入 $x^2$ 并记录 $x$；经过第二条时加入 $2xy+y^2$，然后清除记录。

做法

建立状态 $(u,p)$。$p=0$ 表示当前没有未结算道路；$1\le p\le50$ 表示上一条道路权值为 $p$。

从 $(u,0)$ 经过权值 $w$ 的边到达 $(v,w)$，边权为 $w^2$。从 $(u,p)$ 经过权值 $w$ 的边到达 $(v,0)$，边权为 $2pw+w^2$。所有扩展边权非负，因此从 $(1,0)$ 运行 Dijkstra。城市 $u$ 的答案是状态 $(u,0)$ 的最短距离，其他带未结算权值的状态不能作为合法终点。

正确性证明

任意合法原图路径包含偶数条边。按顺序把每两条边分成一组，扩展图会先记录第一条权值，再在第二条边后回到未记录状态；两次扩展边权之和恰为 $(x+y)^2$。因此每条合法路径对应一条等费用的扩展图路径。

反过来，从未记录状态出发并到达未记录状态的扩展图路径必然交替记录和结算道路，投影回原图后就是按两条道路成组的合法路径，费用也完全相同。Dijkstra 求得扩展图最短路，所以未记录状态的距离就是原问题最小费用。

复杂度

扩展图有 $51n$ 个状态，隐式转移总量为 $O(51m)$。时间复杂度为 $O((n+m)\log n)$（常数含权值范围 $51$），空间复杂度为 $O(n+m)$。