Guest User

Untitled

a guest
Jan 24th, 2018
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include<cstdio>
  2. #include<queue>
  3. #include<cmath>
  4. #include<ctime>
  5. #include<map>
  6. #include<iostream>
  7. #include<algorithm>
  8. #include<vector>
  9. #include<string>
  10. using namespace std;
  11. typedef unsigned long long u64;
  12. const int INF = 1000*1000*1000;
  13. map<string, int> mp;
  14. vector<string> pm;
  15. int _mp = 0;
  16.  
  17. int get_id(string &s)
  18. {
  19.     map<string, int>::iterator it = mp.find(s);
  20.     if(it == mp.end())
  21.     {
  22.         mp[s] = _mp;
  23.         pm[_mp] = s;
  24.         _mp++;
  25.         return _mp-1;
  26.     }
  27.     else
  28.         return it->second;
  29. }
  30.  
  31. string get_name(int id)
  32. {
  33.     return pm[id];
  34. }
  35.  
  36.  
  37. class man
  38. {
  39. public:
  40.     man(int i = 0, int p = 0, int s = 0): id(i), prevsend(p), send(s) {}
  41.     int id;
  42.     int prevsend;
  43.     int send;
  44. };
  45.  
  46. bool operator<(const man &a, const man &b)
  47. {
  48.     return a.send < b.send;
  49. }
  50.  
  51.  
  52. int main()
  53. {
  54.     int n;
  55.     cin >> n;
  56.  
  57.     int m, id;
  58.     string name;
  59.     pm = vector<string> (n);
  60.     vector<vector<int> > g(n);
  61.    
  62.     for(int i = 0; i < n; i++)
  63.     {
  64.         cin >> name >> m;
  65.         id = get_id(name);
  66.         for(int j = 0; j < m; j++)
  67.         {
  68.             cin >> name;
  69.             g[id].push_back(get_id(name));
  70.         }
  71.     }
  72.  
  73.     string message;
  74.     getline(cin, message);
  75.     getline(cin, message);
  76.  
  77.     priority_queue<man> q;
  78.     vector<int> d(n, INF);
  79.  
  80.     q.push(man(0, 0, message.size()));
  81.     d[0] = 0;
  82.  
  83.     while(!q.empty())
  84.     {
  85.         man top = q.top(); q.pop();
  86.         for(int i = 0; i < g[top.id].size(); i++)
  87.         {
  88.             if(d[g[top.id][i]] > top.send && top.send <= 140)
  89.             {
  90.                 d[g[top.id][i]] = top.send;
  91.                 q.push(man(g[top.id][i], top.send, top.send+6+get_name(top.id).size()));
  92.             }
  93.         }
  94.     }
  95.    
  96.     int res = 0;
  97.     for(int i = 0; i < n; i++)
  98.         if(d[i] != INF)
  99.             res++;
  100.  
  101.     cout << res << endl;
  102.     for(int i = 0; i < n; i++)
  103.         if(d[i] != INF)
  104.             cout << get_name(i) << endl;
  105.  
  106.    
  107.     return 0;
  108. }
  109.  
  110. /*
  111. 3
  112. a 1 b
  113. b 1 c
  114. c 0
  115. aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
  116. */
Add Comment
Please, Sign In to add comment