KiK0S

Untitled

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