P4667 电路维修 94分 求调QWQ

#include<bits/stdc++.h>
using namespace std;
struct xzx{
	int u,v,w=1e9,next;
}a[2000005];
int head[2000005],cnt=0,n,m,pb,pa1,pa2;
void add(int u,int v,int w){
	cnt++;
	a[cnt].u=u;
	a[cnt].v=v;
	a[cnt].w=w;
	a[cnt].next=head[u];
	head[u]=cnt;
}
deque<int> q;
int v[2000005],dis[2000005];
void spfa(int s){
	memset(v,0,sizeof(v));
	memset(dis,0x3f,sizeof(dis));
	while (!q.empty())
		q.pop_front();
	q.push_back(s);
	v[s]=1;
	dis[s]=0;
	while (!q.empty()){
		int t=q.front();
		q.pop_front();
		v[t]=0;
		for (int i=head[t];i;i=a[i].next)
			if (dis[a[i].v]>dis[a[i].u]+a[i].w){
				dis[a[i].v]=dis[a[i].u]+a[i].w;
				if (v[a[i].v]==0){
					if (dis[a[i].v]<dis[q.front()])
						q.push_front(a[i].v);
					else
						q.push_back(a[i].v);
					v[a[i].v]=1;
				}
			}
	}
}
int bfs(){
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			char t;
			cin>>t;
			if (t=='/'){
				add((i-1)*(m+1)+j+1,(m+1)*i+j,0);
				add((m+1)*i+j,(i-1)*(m+1)+j+1,0);
				add((i-1)*(m+1)+j,(m+1)*i+j+1,1);
				add((m+1)*i+j+1,(i-1)*(m+1)+j,1);
			}else{
				add((i-1)*(m+1)+j+1,(m+1)*i+j,1);
				add((m+1)*i+j,(i-1)*(m+1)+j+1,1);
				add((i-1)*(m+1)+j,(m+1)*i+j+1,0);
				add((m+1)*i+j+1,(i-1)*(m+1)+j,0);
			}
		}
	}
	spfa(1);
	if(dis[(n+1)*(m+1)]<=(n+1)*(m+1)) 
		cout<<dis[(n+1)*(m+1)];
	else
		cout<<"NO SOLUTION";	
	return 0;
}
int main(){
	cnt=0;
	memset(head,0,sizeof(head));
	bfs();
	return 0;
}