题目链接
思路
把每个点拆成\(5\)个点\(id(x,y),id(x,y)+n,id(x,y)+2*n,id(x,y)+3*n,id(x,y)+4*n\),分别表示到这个点时的方向为上,右,下,左和静止点
非静止点的决策如下:
1.走到对应的同方向的非静止点,代价为\(w\)
2.走到对应的同方向的静止点,代价为\(2w\)
静止点的决策如下:
1.走到四联通的对应方向的非静止点,代价为\(2w\)
2.走到四联通的静止点,代价为\(2w\)
直接建图跑最短路就行了,源点为\((r1,c1)\)对应的静止点,汇点为\((r2,c2)\)对应的静止点
代码:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include