Sunjaree

UVA 336 - A Node Too Far + 762 - We Ship Cheap

Oct 27th, 2020 (edited)
1,262
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. map<int,vector<int>>graph;
  15. map<int,int>visited;
  16.  
  17. int BFS(int root,int ttl){
  18.  
  19.     visited[root] = 0;
  20.     queue<int> que;
  21.     que.push(root);
  22.  
  23.     while (!que.empty()){
  24.  
  25.         int parent = que.front();
  26.         que.pop();
  27.         for(int i=0;i<graph[parent].size();i++){
  28.             int child = graph[parent][i];
  29.             if(child!=root) {
  30.                 if (visited[child] == 0) {
  31.  
  32.                     visited[child] = visited[parent] + 1;
  33.                     que.push(child);
  34.                 }
  35.             }
  36.         }
  37.     }
  38.  
  39.     int count = 0;
  40.     for(auto it=visited.begin();it!=visited.end();it++){
  41.  
  42.         if(it->second>ttl){
  43.             count++;
  44.         } else if(it->second==0 && it->first!=root){
  45.             count++;
  46.         }
  47.     }
  48.  
  49.     return count + (graph.size()-visited.size());
  50. }
  51.  
  52. int main(){
  53.  
  54.     fast;
  55.     int edge;
  56.     int casee = 1;
  57.     while (cin>>edge && edge){
  58.  
  59.         while (edge--){
  60.             int from,to;
  61.             cin>>from>>to;
  62.             graph[from].push_back(to);
  63.             graph[to].push_back(from);
  64.         }
  65.  
  66.         int root,ttl;
  67.         while (cin>>root>>ttl){
  68.             if(root==0 && ttl==0){
  69.                 break;
  70.             }
  71.             cout<<"Case "<<casee<<": "<<BFS(root,ttl)<<" nodes not reachable from node "<<root<<" with TTL = "<<ttl<<".\n";
  72.             visited.clear();
  73.             casee++;
  74.         }
  75.  
  76.         graph.clear();
  77.  
  78.     }
  79.  
  80.     return 0;
  81. }
  82.  
  83.  
  84. ***********************************************************************************************
  85. *************************************762 - We Ship Cheap***************************************
  86.  
  87.  
  88.  
  89. #include<bits/stdc++.h>
  90. using  namespace  std;
  91.  
  92. #define endl     "\n"
  93. #define ll       long long
  94. #define PI       acos(-1.0)
  95. #define test     cout<<"\n****\n"
  96. #define LCM(a,b) ((a/__gcd(a,b))*b)
  97. #define READ(f)  freopen(f, "r", stdin)
  98. #define WRITE(f) freopen(f, "w", stdout)
  99. #define precise  fixed(cout);cout<<setprecision(20)
  100. #define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  101.  
  102.  
  103. map<string,vector<string>> graph;
  104. map<string,bool>visited;
  105. map<string,string> previous;
  106.  
  107. bool BFS(string from,string to){
  108.  
  109.     string root = from;
  110.     visited[from] = true;
  111.  
  112.     queue<string>que;
  113.     que.push(root);
  114.  
  115.     while (!que.empty()){
  116.  
  117.         string parent = que.front();
  118.         que.pop();
  119.  
  120.         for(int i=0;i<graph[parent].size();i++){
  121.             string child = graph[parent][i];
  122.  
  123.             if(!visited[child]) {
  124.                 visited[child] = true;
  125.                 previous[child] = parent;
  126.                 if(child==to){
  127.                     return  true;
  128.                 }
  129.                 que.push(child);
  130.             }
  131.         }
  132.     }
  133.  
  134.     return false;
  135. }
  136.  
  137.  
  138. void path(string from,string to){
  139.  
  140.     if(from==to){
  141.         return;
  142.     }
  143.     path(from,previous[to]);
  144.     cout<<previous[to]<<" "<<to<<endl;
  145. }
  146.  
  147. int main(){
  148.  
  149.     int n;
  150.     bool flag = false;
  151.     while(cin>>n){
  152.  
  153.         for(int i=0;i<n;i++){
  154.  
  155.             string edge1,edge2;
  156.             cin>>edge1>>edge2;
  157.             graph[edge1].push_back(edge2);
  158.             graph[edge2].push_back(edge1);
  159.         }
  160.  
  161.         string from,to;
  162.         cin>>from>>to;
  163.  
  164.         if(!flag) {
  165.             flag = true;
  166.         } else{
  167.             cout<<endl;
  168.         }
  169.  
  170.             if (BFS(from, to)) {
  171.                 path(from, to);
  172.             } else {
  173.                 cout << "No route\n";
  174.             }
  175.  
  176.  
  177.         graph.clear();
  178.         visited.clear();
  179.         previous.clear();
  180.  
  181.     }
  182.     return 0;
  183. }
  184.  
  185.  
RAW Paste Data