苹果可爱

· · 题解

使用一次普通列车是可以用 sosdp 简单解决的。 有个我不会证的性质，就是最多使用普通列车最多 $O(k)$ 次，至少我只能造出 $O(k)$ 次的数据，如果有更强的数据欢迎联系我。 基于这个性质有一个做法，就是每次每次跑完 dij 做一次 sosdp，总共进行 $O(k)$ 次。 复杂度 $O(k((n+m)\log(n+m)+3^k))$，无法通过。 考虑优化建图，把 sosdp 的方式刻画在图上。 图 $1$ 的 $i$ 连到超集，边权为 $0$。 图 $2$ 的 $i$ 连到子集，边权为 $0$。 图 $1$ 的 $i$ 连到图 $2$ 的 $i$，边权为 $a_i$。 原图的 $i$ 连到图 $1$ 的 $c_i$，边权为 $0$。 图 $2$ 的 $x$ 连到所有 $c_i=x$ 的原图的 $i$，边权为 $0$。 直接跑 $dij$ 即可。 复杂度 $O((3^k+n+m)\log (3^k+n+m))$，无法通过。 把上面那个做法的 sosdp 换成 fwt 即可。 复杂度 $O(k2^k+n+m\log (k2^k+n+m))$。 可能略微卡常，因为上一种做法跑的有点快了。 直接一提的是使用 fib 堆优化可以做到更优的复杂度 $O((2^k+n)\log (2^k+n)+k2^k+m)$，但是跑的更慢。