fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. int main() {
  8.     int n, m, virus_index,k;
  9.     cin >> n >>m>>virus_index>>k;
  10.     vector<int> v(n + 1, 0);
  11.     vector<vector<int>> g(n + 1);
  12.     for (int i = 1; i <= n; i++) {
  13.         cin >> v[i];
  14.     }
  15.     for (int i = 1; i <= m; i++) { 
  16.         int u, v;
  17.         cin >> u >> v;
  18.         g[u].push_back(v);
  19.         g[v].push_back(u);
  20.     }
  21.  
  22.     vector<int> lvl(n + 1, 1e8);
  23.     vector<int> used(n + 1, 0); 
  24.     queue<int> q;
  25.     q.push(virus_index);
  26.     lvl[virus_index] = 0;
  27.     used[virus_index] = 1;
  28.     while (!q.empty()) {
  29.         int vertex = q.front();
  30.         q.pop();
  31.         for (auto u : g[vertex]) {
  32.             if (used[u] == 0 && lvl[u] <= k) {  // Check if the node has value 1 and not visited
  33.                 q.push(u);
  34.                 used[u] = 1;
  35.                 lvl[u] = min(lvl[u], lvl[vertex] + 1);
  36.             }
  37.         }
  38.     }
  39.  
  40.  
  41.  
  42.     if (v[1] == 1) {
  43.         q.push(1);
  44.         lvl[1] = 0;
  45.         used[1] = 1;
  46.     }
  47.  
  48.     while (!q.empty()) {
  49.         int vertex = q.front();
  50.         q.pop();
  51.         for (auto u : g[vertex]) {
  52.             if (used[u] == 0 && v[u] == 1) {  // Check if the node has value 1 and not visited
  53.                 q.push(u);
  54.                 used[u] = 1;
  55.                 lvl[u] = min(lvl[u], lvl[vertex] + 1);
  56.             }
  57.         }
  58.     }
  59.  
  60.     for (int i = 1; i <= n; i++) {
  61.         if (lvl[i] >= 1e8) {
  62.             cout << "-1" << " "; 
  63.         } else {
  64.             cout << lvl[i] << " ";
  65.         }
  66.     }
  67.  
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
5 4 4 1
1 1 1 0 0
1 2
2 3
3 4
4 5
stdout
copy 
0 1 2 0 -1
https://ideone.com/lcXNdM
language:
C++14 (gcc 8.3)
created:
12 days 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!