WA on #9

#include<bits/stdc++.h>		//第一次到终点不一定最优 -> 使用优先队列优化 
#define int long long
using namespace std;
const int N=110;
int n,m,a[N][N];
int d[4][2]={1,0,-1,0,0,1,0,-1};  //上下左右 
bool vis[N][N];		//这个格子有没有被走过 
struct node{ 
	int x,y;	//坐标
	int cnt;	//当前花费的金币数 
	int c;		//这一格的颜色
	bool flag;	//这一格是否有使用魔法，1表示有，0表示没有 
};
bool operator < (const node &a,const node &b){		//按金币数升序排序 
	return a.cnt>b.cnt;
}
int bfs(){
	priority_queue<node> q;
	q.push({1,1,0,a[1][1],0});
	vis[1][1]=1; 
	while(!q.empty()){
		node t=q.top();
		q.pop();
		if(t.x==m && t.y==m)
			return t.cnt;
		for(int i=0;i<4;++i){
			int xx=t.x+d[i][0];
			int yy=t.y+d[i][1];
			if(vis[xx][yy]) continue;			//走过了就不需要走了 
			if(xx>=1 && xx<=m && yy>=1 && yy<=m){  //在范围内才搜 
				vis[xx][yy]=1; 
				if(a[xx][yy]!=0){    //有颜色 
					if(a[xx][yy]==t.c)   			//颜色相同 
						q.push({xx,yy,t.cnt,a[xx][yy],0});
					else 							//颜色不同 
						q.push({xx,yy,t.cnt+1,a[xx][yy],0});
				}
				else {				//没有颜色 
					if(!t.flag)		//上一格没有使用魔法 
						q.push({xx,yy,t.cnt+2,a[t.x][t.y],1});
				}
			}
		}
	}
	return -1;
}
signed main(){
	cin>>m>>n;
	for(int i=1;i<=n;++i){
		int x,y,c;
		cin>>x>>y>>c;
		a[x][y]=c+1;  		//1表示红色，2表示黄色，0表示无色 
	}
	cout<<bfs();
	return 0;
}