SP96题解
Isshiki·Iroha
2021-08-23 22:43:03
题目传送门：[SP96](https://www.luogu.com.cn/problem/SP96)
题目要求最短时间，其实就是求最短路，可以用 BFS，先找到起点，以起点为中心，向四个方向拓展，如果没有访问，就加入队列继续更新。但是你不能按板子写，不然会 WA。
如果按板子打，我们很容易（~~困难~~）发现一个问题：对于一个点 $(x,y)$，它第一次被更改后就不再访问了。但是如果后面又有更优解，它就不会继续更新，只会更新 $(x,y)$，所以我们就不用 vis 来判重，能更新就 push。
$10ms$ 代码如下：
```cpp
//只是删除了vis数组，和更改了bfs
void bfs() {
queue<Chtholly>q;
dis[sx][sy]=0;
temp.x=sx;
temp.y=sy;
q.push(temp);
while(!q.empty()) {
Chtholly L=q.front();
q.pop();
ri ux=L.x;
ri uy=L.y;
for(ri i=0; i<4; ++i) {
ri tx=ux+dx[i];
ri ty=uy+dy[i];
if(tx<1||ty<1||tx>n||ty>m||maps[tx][ty]==-1)continue;
if(dis[tx][ty]>dis[ux][uy]+maps[tx][ty]) {
dis[tx][ty]=dis[ux][uy]+maps[tx][ty];
if(tx==ex&&ty==ey)continue;
temp.x=tx;
temp.y=ty;
q.push(temp);
}
}
}
}
```
玄学 $0ms$ 优化：
这里是在[倚栏丶听风](https://www.luogu.com.cn/user/247220)大佬的提示下写的:
**你可以试着在遇到数字大于 $1$ 时，比如 $3$，把这个点视作没访问过，站在原地访问 $2$ 次，最终得到的才是最优解（其实和 SPFA 比较像）。**
因为一个能到终点的点，最多能被更新 $3$ 次，因为有一边是到终点的，不可以更新 $4$ 次，那你一想，万一到这个点的一边有分叉，刚好能连续更新勒？那么那个点到这个点之前已经被更新了。所以至多更新 $3$ 次（我的思路）。
那我们判断 vis 小于 $2$ 就加入队列并标记就可以了（按我的思路改成 $3$ 就可以了）。
最后贴上目前最优解代码:
```cpp
#include<bits/stdc++.h>
#define reg register
#define ri reg int
using namespace std;
const int maxn=26;
const int INF=0x3f3f3f3f;
//bool vis[maxn][maxn];
int vis[maxn][maxn];
int dis[maxn][maxn],maps[maxn][maxn];
int n,m,sx,sy,ex,ey;
const int dx[4]= {0,0,1,-1};
const int dy[4]= {1,-1,0,0};
struct Chtholly {
int x,y;
}temp;
void bfs() {
queue<Chtholly>q;
dis[sx][sy]=0;
vis[sx][sy]=1;
temp.x=sx;
temp.y=sy;
q.push(temp);
while(!q.empty()) {
reg Chtholly L=q.front();
q.pop();
ri ux=L.x;
ri uy=L.y;
for(ri i=0; i<4; ++i) {//四个方向遍历
ri tx=ux+dx[i];
ri ty=uy+dy[i];
if(tx<1||ty<1||tx>n||ty>m||maps[tx][ty]==-1)continue;
if(dis[tx][ty]>dis[ux][uy]+maps[tx][ty]) {
dis[tx][ty]=dis[ux][uy]+maps[tx][ty];
if(tx==ex&&ty==ey)continue;
if(vis[tx][ty]<2) {
temp.x=tx;
temp.y=ty;
q.push(temp);
++vis[tx][ty];
}
}
}
}
}
inline void Memset() {//初始化
for(ri i(1); i<=n; ++i) {
for(ri j(1); j<=m; ++j) {
dis[i][j]=INF;
vis[i][j]=0;
maps[i][j]=0;
}
}
}
int main() {
ios::sync_with_stdio(false);
reg char a;
while(true) {
cin>>m>>n;
if(n==0&&m==0) {
return 0;
}
Memset();//多测不清空，爆零两行泪
for(ri i(1); i<=n; ++i) {
for(ri j(1); j<=m; ++j) {
cin>>a;
if(a=='S')sx=i,sy=j;
else if(a=='D')ex=i,ey=j;
else if(a=='X')maps[i][j]=-1;
else maps[i][j]=a-'0';
}
}
//找起点终点
maps[sx][sy]=0;
maps[ex][ey]=0;
bfs();
cout<<dis[ex][ey]<<endl;
}
return 0;
}
```