题解 | 旺仔哥哥走迷宫

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

int n, m;
int safe[100005];
int dest[100005];

int main () {
	cin >> n >> m;
	vector<vector<int> > graph(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> safe[i];
		safe[i] = 1 - safe[i]; 
	}
	int v1, v2;
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2;
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}
	bool ans = false;
	queue<int> q;
	q.push(1);
	dest[1] = 0;
	memset(dest, 0xFF, sizeof(dest));
	while (!ans && !q.empty()) {
		int v = q.front();
		if (v == n) ans = true; 
		q.pop();
		for (vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++) {
			if (safe[*it] && dest[*it] < 0) {
				q.push(*it);
				dest[*it] = dest[v] + 1;
			}
		}
	}
	cout << (ans ? "Yes" : "No") << endl; 
}