题解 | 旺仔哥哥走迷宫

#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int to,next;
};
int indx=0;
vector<Edge> edge;//链式前向星
int head[100001];
void add(int u,int v){
    edge[indx].to = v;
    edge[indx].next = head[u];
    head[u] = indx++; 
}
bool flag[200001];
int ans=0;
void bfs(vector<int>&a,int begin,int n){
    queue<int> pq;
    pq.push(1);
    while(!pq.empty()){
        int u = pq.front();
        pq.pop();
        if(flag[u]) continue;
        if(u==n){
            ans++;
            return ;
        }
        flag[u]=true;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int to = edge[i].to;
            if(!flag[to]&&a[to]!=1){
                pq.push(to);
            }
        }
    }
}

int main() {
    int n,m;
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    edge = vector<Edge> ((m+1)*2);
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    if(a[1]==1) {
        cout<<"No";
        return 0;
    }
    bfs(a,1,n);
    if(ans>0){
        cout<<"Yes\n";
    }else cout<<"No\n";
}
// 64 位输出请用 printf("%lld")