自动搬运

查看原文

来自洛谷，原作者为

	冯易菜鸡 **

搬运于2025-08-24 21:44:38，当前版本为作者最后更新于2017-08-24 17:11:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

每个点拆成4个

蓝色虚线的边长度为0，橙色实线的边长度为1

然后再在节点中连边，像下图那样

最后建一个超级起点和超级终点，超级起点向原起点的四个节点连边（dis=0），原终点的四个节点向超级中电加边（dis=0）

跑最短路

各组节点之间连变的时候，可以分别按照x和y排序后加变

以样例为例：