Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <unordered_map>
  6. #include <map>
  7. #include <string>
  8. #include <cmath>
  9. #include <deque>
  10. #include <cstring>
  11. #include <set>
  12.  
  13. using namespace std;
  14.  
  15. #define endl '\n'
  16.  
  17. struct troi {
  18.     int first, second, dist;
  19.     troi(int a, int b, int c) : first(a), second(b), dist(c) {}
  20. };
  21.  
  22. bool operator<(const troi a, const troi other) {
  23.         return a.dist < other.dist || (a.dist == other.dist && a.first > other.first)
  24.             || (a.dist == other.dist && a.first == other.first && a.second < other.second);
  25. }
  26.  
  27. //bool cmp(pair<int, string> a, pair<int, string> b) {
  28. //  return a.first > b.first || (a.first == b.first && a.second > b.second);
  29. //}
  30.  
  31. int main () {
  32.     ios::sync_with_stdio(false);
  33.     cin.tie(0);
  34.  
  35.     int n;
  36.     cin >> n;
  37.  
  38.     vector<string> name(n);
  39.     vector<int> ver(n);
  40.     vector<vector<pair<int, string> > > edges(n);
  41.     string s;
  42.     int v;
  43.     map<pair<string, int>, int> num;
  44.     for (int i = 0; i < n; i++) {
  45.         cin >> name[i] >> ver[i];
  46.         int m;
  47.         cin >> m;
  48.         for (int j = 0; j < m; j++) {
  49.             cin >> s >> v;
  50.             edges[i].push_back(make_pair(v, s));
  51.         }
  52.         //sort(edges[i].begin(), edges[i].end(), cmp);
  53.         num[make_pair(name[i], ver[i])] = i;
  54.     }
  55.  
  56.     map<string, bool> used;
  57.     set<troi> q;
  58.     q.insert(troi(ver[0], 0, 0));
  59.     vector<pair<string, int> > ans;
  60.     while (!q.empty()) {
  61.         auto u = *(q.begin());
  62.         if (used.find(name[u.second]) != used.end()) {
  63.             q.erase(u);
  64.             continue;
  65.         }
  66.         used[name[u.second]] = true;
  67.         for (auto v : edges[u.second]) {
  68.             auto ind = num[make_pair(v.second, v.first)];
  69.             q.insert(troi(ver[ind], ind, u.dist + 1));
  70.         }
  71.         if (u.second != 0) {
  72.             ans.push_back(make_pair(name[u.second], u.first));
  73.         }
  74.         q.erase(u);
  75.     }
  76.  
  77.     cout << ans.size() << endl;
  78.     sort(ans.begin(), ans.end());
  79.     for (auto i : ans) {
  80.         cout << i.first << " " << i.second << endl;
  81.     }
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement