fork(5) download
copy 
  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
comments (?)
stdin
copy 
7
Isenbaev Oparin Toropov
Ayzenshteyn Oparin Samsonov
Ayzenshteyn Chevdar Samsonov
Fominykh Isenbaev Oparin
Dublennykh Fominykh Ivankov
Burmistrov Dublennykh Kurpilyanskiy
Cormen Leiserson Rivest
stdout
copy 
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
https://ideone.com/XHozKe
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!