fork(1) download 
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <stdio.h>
  4. #include <queue>
  5.  
  6. #define	N 676			/* all situation for city name */
  7.  
  8. struct node {
  9. 	int cityNumber;
  10. 	struct node *neighbor;
  11. 	int path;
  12. };				/* ----------  end of struct node  ---------- */
  13.  
  14. typedef struct node Node;
  15.  
  16. /* 
  17.  * ===  FUNCTION  ======================================================================
  18.  *         Name:  printAns
  19.  *  Description:  
  20.  * =====================================================================================
  21.  */
  22. 	void
  23. printAns ( Node m[], int start, int end)
  24. {
  25.  
  26. 	int temp1 = 0 ,temp2 = 0;
  27.  
  28. 	if ( start != end ) {
  29. 		printAns( m, start, m[end].path); 
  30. 	}
  31. 	else {
  32. 		return ;
  33. 	}
  34.  
  35. 	temp1 = m[ m[end].path ].cityNumber / 26;
  36. 	temp2 = m[ m[end].path ].cityNumber % 26;
  37. 	printf("%c%c ", temp1+'A', temp2+'A'); 
  38.  
  39. 	temp1 = m[end].cityNumber / 26;
  40. 	temp2 = m[end].cityNumber % 26;
  41. 	printf("%c%c\n", temp1+'A', temp2+'A'); 
  42.  
  43. 	return ;
  44. }		/* -----  end of function printAns  ----- */
  45. /* 
  46.  * ===  FUNCTION  ======================================================================
  47.  *         Name:  bfs
  48.  *  Description:  
  49.  * =====================================================================================
  50.  */
  51. 	void
  52. bfs (bool v[], Node m[], int start, int end )
  53. {
  54. 	int currentCityNum, pathRecord;
  55. 	Node *currentCity;
  56. 	std::queue<int> que;
  57. 	que.push(start);
  58. 	v[start] = true;
  59. 	m[start].path = start;
  60.  
  61. 	if ( start == end ) {
  62. 		int temp1 ,temp2;
  63.  
  64. 		temp1 = m[ start ].cityNumber / 26;
  65. 		temp2 = m[ start ].cityNumber % 26;
  66. 		printf("%c%c ", temp1+'A', temp2+'A'); 
  67.  
  68. 		temp1 = m[end].cityNumber / 26;
  69. 		temp2 = m[end].cityNumber % 26;
  70. 		printf("%c%c\n", temp1+'A', temp2+'A'); 
  71. 		return ;
  72. 	}
  73. 	while ( !que.empty()) {
  74. 		pathRecord = que.front();
  75. 		que.pop();
  76. 		currentCity = &m[pathRecord];	
  77. 		while ( NULL != currentCity ) {
  78. 			currentCityNum = currentCity->cityNumber;
  79. 			if ( !v[currentCityNum]  ) {
  80. 				currentCity->path = pathRecord;
  81. 				m[currentCityNum].path = pathRecord;
  82. 				v[currentCityNum] = true;
  83. 				if ( end == currentCityNum ) {
  84. 					printAns( m, start, end);
  85. 					return ;
  86. 				}
  87. 				else {
  88. 					que.push(currentCityNum);
  89. 				}
  90. 			}
  91. 			currentCity = currentCity->neighbor;
  92. 		}
  93. 	}
  94. 	printf ( "No route\n" );
  95. 	return ;
  96. }		/* -----  end of function bfs  ----- */
  97.  
  98. /* 
  99.  * ===  FUNCTION  ======================================================================
  100.  *         Name:  addEdge
  101.  *  Description:  
  102.  * =====================================================================================
  103.  */
  104. 	void
  105. addEdge (Node map[], int city1, int city2 )
  106. {
  107. 	Node *temp;
  108.         /* city1 -> city2  */
  109. 	temp = (Node*)malloc(sizeof(Node));
  110. 	temp->cityNumber = city2;
  111. 	temp->neighbor = map[city1].neighbor;
  112. 	map[city1].neighbor = temp;	
  113. 	map[city1].cityNumber = city1;
  114.         /* city2 -> city1  */
  115. 	temp = (Node*)malloc(sizeof(Node));
  116. 	temp->cityNumber = city1;
  117. 	temp->neighbor = map[city2].neighbor;
  118. 	map[city2].neighbor = temp;	
  119. 	map[city2].cityNumber = city2;
  120.  
  121. 	return ;
  122. }		/* -----  end of function addEdge  ----- */
  123. /* 
  124.  * ===  FUNCTION  ======================================================================
  125.  *         Name:  main
  126.  *  Description:  
  127.  * =====================================================================================
  128.  */
  129. 	int
  130. main ( int argc, char *argv[] )
  131. {
  132. 	char name1[3], name2[3];
  133. 	int city1 = 0, city2 = 0, datas = 0;
  134. 	bool visit[N];
  135. 	Node map[N];
  136.  
  137. 	while ( scanf ( "%d", &datas )!= EOF ) {
  138.  
  139. 		memset(visit, false, sizeof(bool)*N);
  140. 		for ( int i = 0; i<N; i++ ) {
  141. 			map[i].neighbor = NULL;
  142. 		}
  143. 		for ( int i = 0; i<datas; i++ ) {
  144. 			scanf ( "%s%s", &name1, &name2 ); 
  145. 			city1 = (name1[0]-'A')*26+(name1[1]-'A');
  146. 			city2 = (name2[0]-'A')*26+(name2[1]-'A');
  147. 			addEdge(map, city1, city2);
  148. 		}
  149.  
  150. 		scanf ( "%s%s", &name1, &name2 ); 
  151. 		city1 = (name1[0]-'A')*26+(name1[1]-'A');
  152. 		city2 = (name2[0]-'A')*26+(name2[1]-'A');
  153. 		printf ( "\n" );
  154. 		bfs(visit, map, city1, city2);	
  155. 		printf ( "\n" );
  156. 	}
  157. 	return EXIT_SUCCESS;
  158. }				/* ----------  end of function main  ---------- */
Success #stdin #stdout 0.02s 2728KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/wP5m9
language:
C++ (gcc 8.3)
created:
11 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!