如题,有些状态很容易描述,状态较多,且转移起来较为容易,但不好用dp表述的题目,只要状态数<=1e6,甚至<=1e7,且转移(边)数<=1e6甚至<=1e7,我们就直接最短路做

1.调色题Ⅱ

链接

赛时这题我使用了很奇怪的写法状压,写的很烦,但赛后看题解才发现可以最短路 我们记录a[i]可以到达的所有值域的最短路,如果能访问到的话cnt[值域]++,之后,若cnt[值域]==n,我们就可以利用dis sum[值域]来更新答案了

2.2026杭电春季联赛1.力的平衡

alt

这里有一个引理:

二维 Steinitz 引理给出： 若一组二维向量的和为 0，且每个向量都落在关于原点中心对称的凸集 B 中， 那么存在一种重排，使得所有前缀和都落在 B 中。

那么状态数就只有 200200种,对于一个点有k条边可走,那么复杂度为4e4k 可以跑最短路

#3.蓝桥杯模拟赛1.G

链接

对于测试点1,状态数很小,且每一种状态数最多有12条边,可以最短路