KiK0S

Untitled

Feb 24th, 2018
607
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. map<pair<string, int>, int> id;
  6. vector<vector<int>> g;
  7. map<string, vector<int>> vers;
  8. map<string, int> mins;
  9. signed main() {
  10.     //freopen(".in", "r", stdin);
  11.     //freopen(".out", "w", stdout);
  12.     ios_base::sync_with_stdio(0);
  13.     cin.tie(0);
  14.     cout.tie(0);
  15.     int n;
  16.     cin >> n;
  17.     vector<pair<string, int>> all;
  18.     for(int i = 0; i < n; i++){
  19.         string s;
  20.         int a;
  21.         cin >> s >> a;
  22.         if(!id.count({s,a})){
  23.             id[{s,a}] = g.size();
  24.             g.push_back(vector<int>());
  25.             vers[s].push_back(a);
  26.             all.push_back({s, a});
  27.         }
  28.         int v = id[{s,a}];
  29.         int m;
  30.         cin >> m;
  31.         for(int i = 0; i < m; i++){
  32.             cin >> s >> a;
  33.             if(!id.count({s,a})){
  34.                 id[{s,a}] = g.size();
  35.                 g.push_back(vector<int>());
  36.                 vers[s].push_back(a);
  37.                 all.push_back({s, a});
  38.             }
  39.             g[v].push_back(id[{s,a}]);
  40.         }
  41.     }
  42.     queue<int> q;
  43.     vector<int> dist(n, 1e9);
  44.     map<string, int> used;
  45.     vector<pair<string, int>> ans;
  46.     dist[0] = 0;
  47.     q.push(0);
  48.     while(q.size()){
  49.         int v = q.front();
  50.         q.pop();
  51.         if(used[all[v].first] || mins[all[v].first] != v) continue;
  52.         used[all[v].first] = 1;
  53.         if(dist[v] != 0) ans.push_back(all[v]);
  54.         for(int i = 0; i < g[v].size(); i++){
  55.             if(dist[g[v][i]] > dist[v] + 1){
  56.                 dist[g[v][i]] = dist[v] + 1;
  57.                 q.push(g[v][i]);
  58.                 if(!mins.count(all[g[v][i]].first) || dist[g[v][i]] < dist[mins[all[g[v][i]].first]] || dist[g[v][i]] == dist[mins[all[g[v][i]].first]] && all[mins[all[g[v][i]].first]].second < all[g[v][i]].second){
  59.                     mins[all[g[v][i]].first] = g[v][i];
  60.                 }
  61.             }
  62.         }
  63.     }
  64.     sort(ans.begin(), ans.end());
  65.     cout << ans.size() << '\n';
  66.     for(auto it : ans){
  67.         cout << it.first << ' ' << it.second << '\n';
  68.     }
  69.     return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment