对于一些有限制次数的改变图上的边的题目,将原图复制若干份,也就是若干层,每层之间用特殊的边(题目给出的条件)连接起来,然后再跑最短路。
1.P4568 [JLOI2011] 飞行路线
\(k\) 条航线,我们便在原图的基础上再建立 \(k\) 张子图,共 \(k+1\) 张图,题目给出的特殊条件为转换边权使得其为 \(0\),所以对于一条边 \((u,v,w)\),我们需要在第 \(i、i+1\) 张图之间连一条 \((u_i,v_i+1,0)\) 的边,表示可以用一次机会使得该边边权变为 \(0\)。图建完后,再跑一边最短路统计答案即可,注意 \(k\) 次机会不一定全部用完。
2.[ABC277E] Crystal Switches
考虑将初始可走与初始不可走的边分层,将有开关的点在两层之间连一条边权为 \(0\) 的边,跑最短路。