fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define INF 1e9
  5.  
  6. int main() {
  7.     int n, m;
  8.     cin >> n >> m;
  9.  
  10.     vector<int> a(n + 1);
  11.  
  12.     for (int i = 1; i <= n; i++) {
  13.         cin >> a[i];
  14.     }
  15.  
  16.     vector<vector<int>> adj(n + 1);
  17.  
  18.     for (int i = 0; i < m; i++) {
  19.         int u, v;
  20.         cin >> u >> v;
  21.  
  22.         adj[u].push_back(v);
  23.         adj[v].push_back(u);
  24.     }
  25.  
  26.     int k;
  27.     cin >> k;
  28.  
  29.     // Add super-source 0
  30.     vector<vector<int>> G(n + 1);
  31.  
  32.     for (int i = 1; i <= n; i++) {
  33.         G[i] = adj[i];
  34.  
  35.         if (a[i] == 0) {
  36.             G[0].push_back(i);
  37.             G[i].push_back(0);
  38.         }
  39.     }
  40.  
  41.     // BFS from super-source
  42.     queue<int> q;
  43.     vector<int> dist(n + 1, INF);
  44.  
  45.     q.push(0);
  46.     dist[0] = 0;
  47.  
  48.     while (!q.empty()) {
  49.         int u = q.front();
  50.         q.pop();
  51.  
  52.         for (int v : G[u]) {
  53.             if (dist[v] == INF && dist[u] + 1 <= k + 1) {
  54.                 dist[v] = dist[u] + 1;
  55.                 q.push(v);
  56.             }
  57.         }
  58.     }
  59.  
  60.     // Infect nodes within distance k of a virus
  61.     for (int i = 1; i <= n; i++) {
  62.         if (dist[i] <= k + 1) {
  63.             a[i] = 0;
  64.         }
  65.     }
  66.  
  67.     // BFS from 1 to n
  68.     queue<int> q2;
  69.     vector<int> d(n + 1, INF);
  70.  
  71.     if (a[1] == 1) {
  72.         q2.push(1);
  73.         d[1] = 0;
  74.     }
  75.  
  76.     while (!q2.empty()) {
  77.         int u = q2.front();
  78.         q2.pop();
  79.  
  80.         for (int v : adj[u]) {
  81.             if (a[v] == 1 && d[v] == INF) {
  82.                 d[v] = d[u] + 1;
  83.                 q2.push(v);
  84.             }
  85.         }
  86.     }
  87.  
  88.     cout << (d[n] == INF ? -1 : d[n]) << '\n';
  89. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6 7
1 1 0 1 1 1
1 2
2 3
3 4
4 5
5 6
1 6
2 5
1
stdout
copy 
1
https://ideone.com/9PUXYH
language:
C++ (gcc 8.3)
created:
9 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!