最短路建模

一句话理解

最短路建模：把问题变成走边的代价。

为什么要学

难点在建图不在模板。

讲解

状态当点，花费当边权。拆点：进点出点。

例子

带开关的门：点拆成“有钥匙/无钥匙”。

常见错误

• 硬套 Dijkstra 却图建错。
• 漏边导致 inf。