Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define mp make_pair
  4. #define f first
  5. #define s second
  6. using namespace std;
  7.  
  8. int n, d[1001], c = 0;
  9. bool g[1001][1001], used[1001], disabled[1001];
  10. pair <string, int> l[1001], ans[1001];
  11. queue <int> q;
  12.  
  13. void bfs(int v) {
  14.     used[v] = true;
  15.     d[v] = 0;
  16.     q.push(v);
  17.     while (!q.empty()) {
  18.         int x = q.front();
  19.         q.pop();
  20.         for (int i = 1; i <= n; i++) {
  21.             if (g[x][i] == true && !used[i] && !disabled[i]) {
  22.                 used[i] = true;
  23.                 d[i] = d[x] + 1;
  24.                 q.push(i);
  25.             }
  26.         }
  27.     }
  28. }
  29.  
  30. int main() {
  31.     cin>>n;
  32.     for (int i = 1; i <= n; i++) {
  33.         string name;
  34.         int v, u;
  35.         cin>>name>>v>>u;
  36.         l[i] = mp(name, v);
  37.         for (int j = 1; j <= u; j++) {
  38.             string uname;
  39.             int uv;
  40.             cin>>uname>>uv;
  41.             g[i][j] = true;
  42.         }
  43.     }
  44.     bfs(1);
  45.     for (int i = 1; i <= n; i++) {
  46.         for (int j = 1; j <= n && j != i; j++) {
  47.             if (l[i].f == l[j].f && used[i] && used[j]) {
  48.                 if (d[i] > d[j])
  49.                     disabled[i] = true;
  50.                 else if (d[j] > d[i])
  51.                     disabled[j] = true;
  52.                 else {
  53.                     if (l[i].s > l[j].s)
  54.                         disabled[j] = true;
  55.                     else if (l[i].s < l[j].s)
  56.                         disabled[i] = true;
  57.                 }
  58.             }
  59.         }
  60.     }
  61.     int used[1001] = {};
  62.     int d[1001] = {};
  63.     bfs(1);
  64.     for (int i = 1; i <= n; i++)
  65.         if (used[i]) {
  66.             c++;
  67.             ans[i] = l[i].f;
  68.         }
  69.     sort(ans+1, ans+n);
  70.     cout<<c<<endl;
  71.     for (int i = 1; i <= n; i++)
  72.         cout<<ans[i]<<l[i].s<<" "<<d[i]<<endl;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement