[评测记录](https://www.luogu.org/record/show?rid=11491060)
by tkp875392925 @ 2018-10-05 08:09:11
这是我的
```cpp
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1005;
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
int n,m,jud[M][M],vis[M][M];
struct edge
{
int x,y,col;
int cost,flag;
bool friend operator < (edge a,edge b)
{return a.cost>b.cost;}
}now;
priority_queue<edge>q;
void add1(int a,int b)
{
edge t;
t.flag=0;
if (now.col==jud[a][b])
t.x=a,t.y=b,t.col=now.col,t.cost=now.cost;
else
t.x=a,t.y=b,t.col=jud[a][b],t.cost=now.cost+1;
q.push(t);return ;
}
void add2(int a,int b)
{
edge t;
t.x=a,t.y=b;t.col=now.col;t.flag=1;t.cost=now.cost+2;q.push(t);
if (now.col==1) t.col=2,t.cost=now.cost+3,q.push(t);
else t.col=1,t.cost=now.cost+3,q.push(t);
}
void bfs()
{
now.x=1,now.y=1,now.col=jud[1][1];
now.cost=0;q.push(now);vis[1][1]=1;
while (q.size())
{
now=q.top();q.pop();
if (now.x==n&&now.y==n){cout<<now.cost;return ;}
for (int i=0;i<4;i++)
{
int xx=now.x+fx[i];
int yy=now.y+fy[i];
if (xx>n||yy>n||xx<1||yy<1||vis[xx][yy]) continue;
if (jud[xx][yy]>0) add1(xx,yy),vis[xx][yy]=1;
else if (!now.flag) add2(xx,yy),vis[xx][yy]=1;
}
}
puts("-1");
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if (c==0) jud[a][b]=2;
else jud[a][b]=1;
}
bfs();
return 0;
}
```
by AcerMo @ 2018-10-05 08:25:23