Sunjaree

UVA 567 - Risk

Oct 28th, 2020
593
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using  namespace  std;
  3.  
  4. #define endl     "\n"
  5. #define ll       long long
  6. #define PI       acos(-1.0)
  7. #define test     cout<<"\n****\n"
  8. #define LCM(a,b) ((a/__gcd(a,b))*b)
  9. #define READ(f)  freopen(f, "r", stdin)
  10. #define WRITE(f) freopen(f, "w", stdout)
  11. #define precise  fixed(cout);cout<<setprecision(20)
  12. #define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  13.  
  14.  
  15. #define MAX 30
  16. vector<int>graph[MAX];
  17. int distan[MAX];
  18.  
  19. int BFS(int from,int to){
  20.  
  21.     memset(distan,-1,sizeof(distan));
  22.     int root = from;
  23.     distan[root] = 0;
  24.  
  25.     queue<int>que;
  26.     que.push(root);
  27.  
  28.     while (!que.empty()){
  29.  
  30.         int parent = que.front();
  31.         que.pop();
  32.  
  33.         for(int i=0;i<graph[parent].size();i++){
  34.             int child = graph[parent][i];
  35.  
  36.             if(distan[child]==-1){
  37.                 distan[child] = distan[parent] + 1;
  38.                 que.push(child);
  39.             }
  40.         }
  41.     }
  42.  
  43.     return distan[to];
  44. }
  45.  
  46. int main(){
  47.  
  48.     //WRITE("outhudai.txt");
  49.     //fast;
  50.     int n,casee = 1;
  51.  
  52.     while(cin>>n){
  53.  
  54.         for(int i=0;i<n;i++){
  55.             int edge;
  56.             cin>>edge;
  57.             graph[1].push_back(edge);
  58.             graph[edge].push_back(1);
  59.         }
  60.  
  61.  
  62.         for(int i=2;i<20;i++){
  63.             cin>>n;
  64.             for(int j=0;j<n;j++){
  65.                 int edge;
  66.                 cin>>edge;
  67.                 graph[i].push_back(edge);
  68.                 graph[edge].push_back(i);
  69.             }
  70.         }
  71.  
  72.         int query;
  73.         cin>>query;
  74.         cout<<"Test Set #"<<casee<<endl;
  75.         for(int i=0;i<query;i++){
  76.             int from,to;
  77.             cin>>from>>to;
  78.  
  79.             printf("%2d to %2d: %d\n",from,to,BFS(from,to));
  80.         }
  81.         cout<<endl;
  82.         for(auto& it: graph){
  83.             it.clear();
  84.         }
  85.         casee++;
  86.     }
  87.  
  88.  
  89.     return 0;
  90. }
  91.  
  92.  
RAW Paste Data