题解 P3036 【[USACO16DEC]Lasers and Mirrors激光和镜子】

· · 题解

每个点拆成4个

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

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

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

跑最短路

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

以样例为例：