STL 的 `priority_queue` 默认是大根堆，所以要把 `<` 重载成 `>`，把优先队列变成小根堆
by TheSky233 @ 2023-01-13 11:25:01
这个大于号小于号决定的应该是优先级吧
这个题我没做过捏
by XOOR @ 2023-01-13 11:26:44
@[Chancylaser](/user/241817) 诶这题为什么要重载
by XOOR @ 2023-01-13 11:28:30
@[TheSky233](/user/501865) 嗯，我刚才想了想明白了，此贴结
by Chancylaser @ 2023-01-13 11:28:43
@[Apollo_tyr](/user/450743) 其实普通队列就可以通过了，我这个优先队列写假了
by Chancylaser @ 2023-01-13 11:29:12
@[Chancylaser](/user/241817) 我写了个dfs
by XOOR @ 2023-01-13 11:31:15
```cpp
#include<cstdio>
#include<queue>
#include<iostream>
#define Min(x,y) x<y?x:y
using namespace std;
const int N=1100;
int n,m,minn=0x7fffffff;
int a[N][N],vis[N][N],jz_minn[N][N],dx[5]{0,0,0,1,-1},dy[5]{0,1,-1,0,0};
//queue<node> q;
void dfs(int x,int y,int t,int c){
if(x==m && y==m){
minn=Min(minn,t);
return ;
}
for(int i=1;i<=4;i++){
int fx=x+dx[i],fy=y+dy[i];
if(fx>0 && fy>0 && fx<=m && fy<=m && !vis[fx][fy] && (a[x][y] || a[fx][fy])){
if(!a[fx][fy]){
if(t+2<jz_minn[fx][fy]){
vis[fx][fy]=1;
jz_minn[fx][fy]=t+2;
dfs(fx,fy,t+2,c);
vis[fx][fy]=0;
}
}else{
if(c==a[fx][fy] && t<jz_minn[fx][fy]){
vis[fx][fy]=1;
jz_minn[fx][fy]=t;
dfs(fx,fy,t,c);
vis[fx][fy]=0;
}else if(c+1<minn && c+1<jz_minn[fx][fy]){
vis[fx][fy]=1;
jz_minn[fx][fy]=t+1;
dfs(fx,fy,t+1,a[fx][fy]);
vis[fx][fy]=0;
}
}
}
}
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
jz_minn[i][j]=0x7fffffff;
}
}
for(int i=1;i<=n;i++){
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
a[x][y]=c+1;
}
vis[1][1]=1;
dfs(1,1,0,a[1][1]);
// printf("%d%d",n,m);
if(minn==0x7fffffff){
printf("-1");
return 0;
}
printf("%d",minn);
return 0;
}
by XOOR @ 2023-01-13 11:31:33