P2226 [HNOI2001] 遥控赛车比赛 dijkstra最短路题解
看了一下基本没有最短路题解。唯一的一篇最短路题解已经是 19 年的 spfa 做法了，那我写一篇 dij 的。
首先说明，其实你 dij 要是会写了，记忆化搜索思路只会更加简单。无论是设计还是转移状态思路都是水到渠成。
总思路就是在 dij 里面传一个反应时间进去，跑最短路。总共跑
我们思考一下 dij 的贪心原理，即我们会从所有点状态中挑选一个最优的出来，这个最优的保证一定不可能被其他状态松弛成更优了，所以这个状态标记定死，然后用它松弛别的点更新状态并重复
那我们考虑一下这道题的状态。如何确定某个状态一定是全局最优了呢？首先我们要有这个点对吧。那光有这个点够不够？考虑以下情形。
这两种路径都走到了节点
很明显，我们假设反应速度为
所以容易想到，我们需要记录保持当前方向不变的时间，也就是我们已经使用当前方向走了多远了。为了判定在本轮转移中是否改变当前方向，更新这个维度的状态，我们还需要记录当前方向。
现在就容易发现我们已经保证了每个状态确定的时候一定是最优的了。这是类似 dp 的思路。
这个时候考虑转移；转移非常简单，远古绿题他一般就是板子变一变加个维度，改个状态，不会怎么为难你。
设当前反应时间为
-
保持当前方向不变继续走。
那么
t 自增，pt 自增（如果已经达到当前反应速度的冷却期了可以就设置为反应速度，不加了，节省空间），pos 按照方向变，way 不变。 -
改变方向。
那么前提条件是
pt\geq T 。如果满足的话，那么t 自增，pt 置为1 ，pos 按照方向变，way 按照方向变。
最后，如果跑到终点就更新一下值。那么就做完了。
题外话：是谁因为把坐标二维压一维，结果数组那一维开的又是
我真服了这个越界竟然不报 RE 报 WA，我还以为是写错了
如果以后发现类似你对数组 0x3f结果访问
码风比较猎奇可能 可以丢给 ai 优化一下。声明：代码注释是 doubao 加的 已经过人工复核确认无误。
温馨提示一下，dist 转移的语句我都写的是上个 dist 数组转移而来，其实时间都已经被存在t1.a中了，你也可以直接写dist=t1.a+1，更加简洁。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define mid (pl+pr>>1)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N=110,mod=998244353;
const ll INF=1e15;
// dist[pos][cnt][dir]:pos代表当前格子编号,cnt当前方向已经走了多少秒,dir当前朝向;值为到达该状态花费的最少时间
int n,m,s1,s2,t1,t2,s,t,dist[N*N][11][4],v[N*N][11][4],a[N][N],ans,res,mp[N][N];
// 优先队列存储:{已经耗费时间,当前方向已行走时长,格子编号,行进方向}
struct node{
int a,b,c,d;
bool operator >(const node &W) const{
return a>W.a;
}
};priority_queue<node,vector<node>,greater<node> > q;
// 四个移动方向:右、下、左、上
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
// 将二维坐标(x,y)压缩成一维格子编号
inline int pt(int x,int y){return (x-1)*m+y;}
// 根据一维编号还原出二维坐标
inline pii wg(int x){return make_pair(((x-1)/m)+1,((x-1)%m)+1);}
// 对给定的反应时间tim跑一次dijkstra求起点到终点最短耗时
void dijkstra(int tim){
// res保存起点抵达终点的最小时间,初始化为极大值
res=0x3f3f3f3f;
// 最短路数组初始化为无穷、访问标记清空
memset(dist,0x3f,sizeof dist);memset(v,0,sizeof v);
// 起点一开始四个方向都可以作为初始行进方向,起步算作一次换向
q.push({0,0,s,0});q.push({0,0,s,1});q.push({0,0,s,2});q.push({0,0,s,3});
dist[s][0][0]=0;dist[s][0][1]=0;dist[s][0][2]=0;dist[s][0][3]=0;
while(!q.empty()){
auto t1=q.top();q.pop();
// 该状态已经取出过最短路,直接跳过
if(v[t1.c][t1.b][t1.d]) continue;
v[t1.c][t1.b][t1.d]=1;
// 当前位置是终点,更新答案最小值
if(t1.c==t){res=min(res,t1.a);}
// 把一维编号解开为二维坐标
pii ps=wg(t1.c);
mp[ps.fi][ps.se]=min(mp[ps.fi][ps.se],t1.a);
// 当前方向持续行走时长还没到达反应时间上限,可以继续沿着原方向往前走一格
if(t1.b<tim){
int nx=ps.fi+dx[t1.d],ny=ps.se+dy[t1.d];
// 新坐标合法、该位置不是障碍物、新状态可以松弛
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]&&!v[pt(nx,ny)][t1.b+1][t1.d]&&dist[pt(nx,ny)][t1.b+1][t1.d]>dist[t1.c][t1.b][t1.d]+1){
q.push({t1.a+1,t1.b+1,pt(nx,ny),t1.d});
dist[pt(nx,ny)][t1.b+1][t1.d]=dist[t1.c][t1.b][t1.d]+1;
}
}else{
// 已经走满反应时间,此时可以更换行进方向,枚举四个朝向
for(int i=0;i<4;i++){
int nx=ps.fi+dx[i],ny=ps.se+dy[i];
int fl=0;
// 新格子坐标合法且不是障碍
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]){
if(i==t1.d){
// 依旧沿用旧方向,继续累加行走计时
if(!v[pt(nx,ny)][tim][t1.d]&&dist[pt(nx,ny)][tim][t1.d]>dist[t1.c][tim][t1.d]+1){
q.push({t1.a+1,tim,pt(nx,ny),t1.d});
dist[pt(nx,ny)][tim][t1.d]=dist[t1.c][tim][t1.d]+1;
}
}else{
// 更换了新方向,新方向已行走时长重置为1
if(!v[pt(nx,ny)][1][i]&&dist[pt(nx,ny)][1][i]>dist[t1.c][tim][t1.d]+1){
q.push({t1.a+1,1,pt(nx,ny),i});
dist[pt(nx,ny)][1][i]=dist[t1.c][tim][t1.d]+1;
}
}
}
}
}
}
}
int main(){
fst
// 读入场地长宽、起点坐标、终点坐标
cin>>n>>m>>s1>>s2>>t1>>t2;
// 起点、终点转为一维压缩编号
s=pt(s1,s2);t=pt(t1,t2);
// 读取地图,a[x][y]=1代表可通行,0代表障碍物
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
// 枚举所有1~10的反应时间
for(int i=1;i<=10;i++){
dijkstra(i);
// res依旧是极大值代表该反应时长下不存在可行路线,直接结束程序
if(res>=10000){return 0;}
// 输出当前反应时间和对应的最短耗时
cout<<i<<" "<<res<<"\n";
}
return 0;
}