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

每个点拆成4个  蓝色虚线的边长度为0，橙色实线的边长度为1 然后再在节点中连边，像下图那样  最后建一个超级起点和超级终点，超级起点向原起点的四个节点连边（dis=0），原终点的四个节点向超级中电加边（dis=0） 跑最短路 各组节点之间连变的时候，可以分别按照x和y排序后加变 以样例为例：