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_node, k;
  9.     cin >> n >> m;
  10.  
  11.     vector<int> v(n + 1, 0);
  12.     vector<vector<int>> g(n + 2);
  13.     for (int i = 1; i <= n; i++) {
  14.         cin >> v[i];
  15.     }
  16.     for (int i = 1; i <= m; i++) {
  17.         int u, v;
  18.         cin >> u >> v;
  19.         g[u].push_back(v);
  20.         g[v].push_back(u);
  21.     }
  22.     cin>>virus_node >> k;
  23.     vector<int> virus(virus_node + 1); 
  24.     for (int i = 1; i <= virus_node; i++) {
  25.         cin >> virus[i];
  26.         g[n + 1].push_back(virus[i]); 
  27.         g[virus[i]].push_back(n + 1);
  28.     }
  29.  
  30.  
  31.     vector<int> lvl(n + 2, 1e8);  
  32.     vector<int> used(n + 2, 0); 
  33.     queue<int> q;
  34.  
  35.     q.push(n + 1);
  36.     lvl[n + 1] = 0;
  37.     used[n + 1] = 1;
  38.  
  39.     while (!q.empty()) {
  40.         int vertex = q.front();
  41.         q.pop();
  42.  
  43.         for (auto u : g[vertex]) {
  44.             if (used[u] == 0 && lvl[vertex] < k) {  // If not visited and within k distance
  45.                 q.push(u);
  46.                 used[u] = 1;
  47.                 lvl[u] = min(lvl[u], lvl[vertex] + 1);
  48.             }
  49.         }
  50.     }
  51.  
  52.     if (v[1] == 1) {
  53.         q.push(1);
  54.         lvl[1] = 0;
  55.         used[1] = 1;
  56.     }
  57.  
  58.     while (!q.empty()) {
  59.         int vertex = q.front();
  60.         q.pop();
  61.  
  62.         for (auto u : g[vertex]) {
  63.             if (used[u] == 0 && v[u] == 1) {
  64.                 q.push(u);
  65.                 used[u] = 1;
  66.                 lvl[u] = min(lvl[u], lvl[vertex] + 1);
  67.             }
  68.         }
  69.     }
  70.  
  71.     for (int i = 1; i <= n; i++) {
  72.         if (lvl[i] >= 1e8) {
  73.             cout << "-1" << " ";  // If the node is unreachable
  74.         } else {
  75.             cout << lvl[i] << " ";  // Otherwise, print the distance
  76.         }
  77.     }
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
4 3
1 1 1 1
1 2
2 3
3 4
1 1
3
stdout
copy 
0 1 1 -1
https://ideone.com/KD2QIj
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!