zyz_yuanzhe

最短路

二分(1) 启发式合并类(1) 哈希(1) 线段树(1) 题解(2)

/ 注册

全部文章 / 最短路（共2篇）

不容易看出是最短路的题目,但可以用最短路做

如题,有些状态很容易描述,状态较多,且转移起来较为容易,但不好用dp表述的题目,只要状态数<=1e6,甚至<=1e7,且转移(边)数<=1e6甚至<=1e7,我们就直接最短路做 1.调色题Ⅱ 链接赛时这题我使用了很奇怪的写法状压,写的很烦,但赛后看题解才发现可以最短路我们...

2026-04-09

0 15

最短路中的虚拟点(中转站)

前言:我们再做一些最短路题目时候,往往会因为一些特殊限制导致建的边太多,所以我们建立一种虚拟点作为中转站,大大减少边数 1.HDU春季联赛10.小塔的梦境迷宫题面: 对于走的边数为%3=0,%3=1,%3=2的情况,可以直接拆点,但是如果对于"瞬移"这种情况要建图,那最坏情况将会多见nn条边,所...

2026-04-09

0 19