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;
- map<string, int> mins;
- 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;
- vector<pair<string, int>> all;
- 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);
- all.push_back({s, 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);
- all.push_back({s, a});
- }
- g[v].push_back(id[{s,a}]);
- }
- }
- queue<int> q;
- vector<int> dist(n, 1e9);
- map<string, int> used;
- vector<pair<string, int>> ans;
- dist[0] = 0;
- q.push(0);
- while(q.size()){
- int v = q.front();
- q.pop();
- if(used[all[v].first] || mins[all[v].first] != v) continue;
- used[all[v].first] = 1;
- if(dist[v] != 0) ans.push_back(all[v]);
- 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]);
- 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){
- mins[all[g[v][i]].first] = g[v][i];
- }
- }
- }
- }
- 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