当一张图的边权只有 \(0\) 和 \(1\) 时，跑 dij 的堆优化显得比较累赘。因为只有两个取值，所以取 \(0\) 的时候在队列前面推进来，反之在后面。其他和 dij 没什么区别，时间复杂度 \(O(m)\)，其中 \(m\) 是边数。
相关题目：P4554 小明的游戏。
点击查看代码
void work() {
m0(vis); mem(dis,0x3f);
For(i,0,n-1) For(j,0,m-1) cin>>ch[i][j];
cin>>stx>>sty>>edx>>edy; dis[stx][sty]=0;
deque<node>q; while(!q.empty()) q.pop_front();
q.push_front({stx,sty});
while(!q.empty()) {
auto [x,y]=q.front(); q.pop_front();
// cout<<x<<' '<<y<<'\n';
if(vis[x][y]) continue;
vis[x][y]=1;
For(i,1,4) {
int X=x+dx[i],Y=y+dy[i];
if(X>=n||X<0||Y>=m||Y<0) continue;
int val=(ch[x][y]!=ch[X][Y]);
if(dis[x][y]+val>=dis[X][Y]) continue;
dis[X][Y]=dis[x][y]+val;
if(ch[x][y]==ch[X][Y]) {
q.push_front({X,Y});
} else {
q.push_back({X,Y});
}
}
}
cout<<dis[edx][edy]<<'\n';
}