fork(5) download
  1. # include <iostream>
  2. # include <string>
  3. # include <cstdio>
  4. # include <vector>
  5. # include <map>
  6. # include <queue>
  7. # include <limits>
  8. # include <algorithm>
  9. using namespace std;
  10. struct Node
  11. {
  12. Node (string str1, int dist1 = 0) {str = str1; dist = dist1;}
  13. string str;
  14. int dist;
  15. };
  16. map <string, map<string, int> > Map;
  17. map <string, int> result;
  18. vector <string> visited;
  19. int main ()
  20. {
  21. //freopen ("1837_isenbaev_number_input.txt", "r", stdin);
  22. //freopen ("1837_isenbaev_number_output.txt", "w", stdout);
  23. int total;
  24. cin >> total;
  25. while (total--)
  26. {
  27. string str1, str2, str3;
  28. cin >> str1 >> str2 >> str3;
  29. Map[str1][str2] = 1;
  30. Map[str1][str3] = 1;
  31. Map[str2][str1] = 1;
  32. Map[str2][str3] = 1;
  33. Map[str3][str1] = 1;
  34. Map[str3][str2] = 1;
  35. result [str1] = result [str2] = result [str3] = numeric_limits<int>::max();
  36. }
  37. queue <Node> Queue;
  38. map <string, int> root = Map ["Isenbaev"];
  39. //result ["Isenbaev"] = 0;
  40. for (map <string, int>::iterator it = root.begin(); it != root.end(); it++)
  41. {
  42. result[it->first] = 1;
  43. Queue.push (Node (it->first, 1));
  44. //cout << "Initial : " << it->first << endl;
  45. }
  46. while (Queue.empty() == false)
  47. {
  48. Node current = Queue.front();
  49. //cout << "Popping : " << current.str << " with " << current.dist << endl;
  50. Queue.pop();
  51. if (find (visited.begin(), visited.end(), current.str) != visited.end())
  52. continue;
  53. for (map <string, int>::iterator it = Map[current.str].begin(); it != Map[current.str].end(); it++)
  54. {
  55. //cout << "Processing : " << it->first << endl;
  56. //if (find (visited.begin(), visited.end(), it->first) == visited.end())
  57. //{
  58. //cout << "Data : " << it->first << ", Count : " << current.dist + 1 << ", Actual : " << result[it->first] << endl;
  59. if (current.dist + 1 < result[it->first])
  60. {
  61. result[it->first] = current.dist + 1;
  62. }
  63. Queue.push (Node (it->first, min (result[it->first], current.dist + 1)));
  64. //}
  65. }
  66. visited.push_back (current.str);
  67. }
  68. for (map <string, int>::iterator it = result.begin(); it != result.end(); it++)
  69. {
  70. if (it->second == numeric_limits<int>::max() && it->first != "Isenbaev")
  71. cout << it->first << " undefined" << endl;
  72. else
  73. if (it->first == "Isenbaev")
  74. cout << it->first << " 0" << endl;
  75. else
  76. cout << it->first << " " << it->second << endl;
  77. }
  78. }
Success #stdin #stdout 0.01s 2832KB
stdin
7
Isenbaev Oparin Toropov
Ayzenshteyn Oparin Samsonov
Ayzenshteyn Chevdar Samsonov
Fominykh Isenbaev Oparin
Dublennykh Fominykh Ivankov
Burmistrov Dublennykh Kurpilyanskiy
Cormen Leiserson Rivest
stdout
Ayzenshteyn 2
Burmistrov 3
Chevdar 3
Cormen undefined
Dublennykh 2
Fominykh 1
Isenbaev 0
Ivankov 2
Kurpilyanskiy 3
Leiserson undefined
Oparin 1
Rivest undefined
Samsonov 2
Toropov 1