fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. int main() {
  5.   int n,m;
  6.   cin>>n>>m;
  7.  
  8. vector<int>a(n);
  9.   for(int i = 0 ; i< n  ;i++){
  10.   	cin>>a[i];
  11.   }
  12.  
  13.   vector<vector<int>>adj(n);
  14.   for(int i = 0 ; i<m ;i++){
  15.   	int u,v;
  16.   	cin>>u>>v;
  17.  
  18.   	adj[u].push_back(v);
  19.   	adj[v].push_back(u);
  20.   }
  21.  
  22.   vector<int>lvl(n,1e9);
  23.   vector<int>used(n,0);
  24.   queue<int>q;
  25.   if(a[0]==1){
  26.   	q.push(0);
  27.   	used[0]=1;
  28.   	lvl[0]=0;
  29.   }
  30.  
  31.   while(!q.empty()){
  32.   	auto u = q.front();
  33.   	q.pop();
  34.  
  35.   	for(auto v: adj[u]){
  36.   	if(a[v]==1 && used[v]==0){
  37.   		used[v]=1;
  38.   		q.push(v);
  39.   		lvl[v]=lvl[u]+1;
  40.   	}
  41.  
  42.   	}
  43.   }
  44.  
  45.   if(lvl[n-1]==1e9){
  46.   	cout<<-1;
  47.   }else{
  48.   	cout<<lvl[n-1];
  49.   }
  50. }
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
5 4
1 1 1 1 1
0 1
0 2
1 3
1 4
stdout
copy 
2
https://ideone.com/Nw8dBE
language:
C++ (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!