题解 P3036 【[USACO16DEC]Lasers and Mirrors激光和镜子】
冯易菜鸡
2017-08-24 17:11:49
每个点拆成4个
![](https://cdn.luogu.com.cn/upload/pic/7360.png)
蓝色虚线的边长度为0,橙色实线的边长度为1
然后再在节点中连边,像下图那样
![](https://cdn.luogu.com.cn/upload/pic/7362.png)
最后建一个超级起点和超级终点,超级起点向原起点的四个节点连边(dis=0),原终点的四个节点向超级中电加边(dis=0)
跑最短路
各组节点之间连变的时候,可以分别按照x和y排序后加变
以样例为例:
![](https://cdn.luogu.com.cn/upload/pic/7368.png)