Advertisement
Josif_tepe

Untitled

Oct 12th, 2023
813
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <set>
  5. #include <fstream>
  6. using namespace std;
  7. const int maxn=5555;
  8. const int INF = 2e9;
  9. vector<pair<int, int> > graph[maxn];
  10. int bfs(int S, int k) {
  11.     vector<bool> visited(maxn, false);
  12.     visited[S] = true;
  13.     queue<int> q;
  14.     q.push(S);
  15.     q.push(INF);
  16.     int res = 0;
  17.     while(!q.empty()) {
  18.         int node = q.front();
  19.         q.pop();
  20.         int dist = q.front();
  21.         q.pop();
  22.        
  23.         if(node != S and dist >= k) {
  24.             res++;
  25.         }
  26.         for(int i = 0; i < (int) graph[node].size(); i++) {
  27.             int neighbour = graph[node][i].first;
  28.             int weight = graph[node][i].second;
  29.            
  30.             if(!visited[neighbour]) {
  31.                 visited[neighbour] = true;
  32.                 q.push(neighbour);
  33.                 q.push(min(dist, weight));
  34.             }
  35.         }
  36.     }
  37.     return res;
  38. }
  39. int main() {
  40.     ifstream cin("mootube.in");
  41.     ofstream cout("mootube.out");
  42.     int n, q;
  43.     cin >> n >> q;
  44.    
  45.     for(int i = 0; i < n - 1; i++) {
  46.         int a, b;
  47.         cin >> a >> b;
  48.         a--; b--;
  49.         int k;
  50.         cin >> k;
  51.        
  52.         graph[a].push_back(make_pair(b, k));
  53.         graph[b].push_back(make_pair(a, k));
  54.     }
  55.    
  56.     for(int i = 0; i < q; i++) {
  57.         int a, k;
  58.         cin >> k >> a;
  59.         a--;
  60.        
  61.         cout << bfs(a, k) << endl;
  62.        
  63.     }
  64.    
  65.     return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement