Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- map<pair<string, int>, int> id;
- vector<vector<int>> g;
- map<string, vector<int>> vers;
- signed main() {
- //freopen(".in", "r", stdin);
- //freopen(".out", "w", stdout);
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- for(int i = 0; i < n; i++){
- string s;
- int a;
- cin >> s >> a;
- if(!id.count({s,a})){
- id[{s,a}] = g.size();
- g.push_back(vector<int>());
- vers[s].push_back(a);
- }
- int v = id[{s,a}];
- int m;
- cin >> m;
- for(int i = 0; i < m; i++){
- cin >> s >> a;
- if(!id.count({s,a})){
- id[{s,a}] = g.size();
- g.push_back(vector<int>());
- vers[s].push_back(a);
- }
- g[v].push_back(id[{s,a}]);
- }
- }
- queue<int> q;
- vector<int> dist(n, 1e9);
- vector<int> used(n);
- dist[0] = 0;
- q.push(0);
- while(q.size()){
- int v = q.front();
- q.pop();
- if(used[v]) continue;
- used[v] = 1;
- for(int i = 0; i < g[v].size(); i++){
- if(dist[g[v][i]] > dist[v] + 1){
- dist[g[v][i]] = dist[v] + 1;
- q.push(g[v][i]);
- }
- }
- }
- vector<pair<string, int>> ans;
- for(auto it : vers){
- int idx = 0;
- int _min = 1e9;
- for(int i = 0; i < it.second.size(); i++){
- int a = it.second[i];
- int v = id[{it.first, a}];
- if(dist[v] < _min || dist[v] == _min && a > idx){
- idx = a;
- _min = dist[v];
- }
- }
- if(_min != 1e9 && _min != 0) ans.push_back({it.first, idx});
- }
- sort(ans.begin(), ans.end());
- cout << ans.size() << '\n';
- for(auto it : ans){
- cout << it.first << ' ' << it.second << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment