Advertisement
Josif_tepe

Untitled

Mar 17th, 2022
629
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <queue>
  6.  
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. #define pb push_back
  12. #define mp make_pair
  13. #define f first
  14. #define s second
  15. int mat[100005][101];
  16.  
  17. int main()
  18. {
  19.     ios_base::sync_with_stdio(false);
  20.     cout.tie(0);
  21.     cin.tie(0);
  22.  
  23.     int n, m, k, s;
  24.     cin >> n >> m >> k >> s;
  25.     vector<int> type;
  26.     for(int i = 0; i < n; i++){
  27.         int a;
  28.         cin >> a;
  29.         type.pb(a-1);
  30.     }
  31.     vector<int> graph[n+5];
  32.     for(int i = 0; i < m; i++){
  33.         int a, b;
  34.         cin >> a >> b;
  35.         graph[a-1].pb(b-1);
  36.         graph[b-1].pb(a-1);
  37.     }
  38.    
  39.     memset(mat, -1, sizeof mat);
  40.     for(int i = 0; i < k; i++){
  41.         queue<int> q;
  42.         vector<bool> visited(n, false);
  43.  
  44.         for(int j = 0; j < n; j++){
  45.             if(type[j] == i) {
  46.            
  47.             q.push(j);
  48.             q.push(0);
  49.             visited[j] = true;
  50.            
  51.         }
  52.            
  53.     }
  54.         while(!q.empty()){
  55.             int c = q.front(); q.pop();
  56.             int dist = q.front(); q.pop();
  57.             mat[c][i] = dist;
  58.             for(int l = 0; l < (int) graph[c].size(); l++){
  59.                 int z = graph[c][l];
  60.                 if(visited[z]) continue;
  61.                 visited[z] = true;
  62.                 q.push(z);
  63.                 q.push(dist+1);
  64.             }
  65.         }
  66.    
  67.     }
  68.    
  69.     for(int i = 0; i < n; i++){
  70.         sort(mat[i], mat[i] + k);
  71.     }
  72.     for(int i = 0; i < n; i++){
  73.         int dist = 0;
  74.         int z = 0;
  75.         for(int j = 0; j < k; j++){
  76.             dist += mat[i][j];
  77.             z++;
  78.             if(z == s) break;
  79.         }
  80.         cout << dist << " ";
  81.     }
  82.    
  83.     return 0;
  84.  
  85. }
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement