Advertisement
mickypinata

USACO-T034: Controlling Companies

Dec 15th, 2021
395
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: concom
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. typedef pair<int, int> pii;
  11.  
  12. const int N = 100 + 5;
  13.  
  14. vector<pii> adj[N];
  15. int con[N];
  16.  
  17. void BFS(int st){
  18.     for(int u = 0; u <= 100; ++u){
  19.         con[u] = 0;
  20.     }
  21.     con[st] = 100;
  22.     vector<int> ans;
  23.     queue<int> que;
  24.     que.push(st);
  25.     while(!que.empty()){
  26.         int u = que.front();
  27.         que.pop();
  28.         if(u != st){
  29.             ans.push_back(u);
  30.         }
  31.         for(pii nxt : adj[u]){
  32.             int v = nxt.first;
  33.             int w = nxt.second;
  34.             if(con[v] <= 50){
  35.                 con[v] += w;
  36.                 if(con[v] > 50){
  37.                     que.push(v);
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     sort(ans.begin(), ans.end());
  43.     for(int x : ans){
  44.         cout << st << ' ' << x << '\n';
  45.     }
  46. }
  47.  
  48. int main(){
  49.     freopen("concom.in", "r", stdin);
  50.     freopen("concom.out", "w", stdout);
  51.  
  52.     int Q;
  53.     scanf("%d", &Q);
  54.     while(Q--){
  55.         int u, v, w;
  56.         scanf("%d%d%d", &u, &v, &w);
  57.         adj[u].emplace_back(v, w);
  58.     }
  59.     for(int u = 1; u <= 100; ++u){
  60.         BFS(u);
  61.     }
  62.  
  63.     fclose(stdin);
  64.     fclose(stdout);
  65.     return 0;
  66. }
  67.  
Advertisement
RAW Paste Data Copied
Advertisement