fork download
copy 
  1. // http://l...content-available-to-author-only...u.tw/homework/q762.htm
  2.  
  3. #include <cstdio>
  4.  
  5. // queue
  6. int idque[26*26] = {0};
  7. int first = 0;
  8. int last = 0;
  9.  
  10. int qempty(){
  11. 	return first == last;
  12. }
  13.  
  14. int qget(){
  15. 	if(qempty()){
  16. 		return -1;
  17. 	}
  18. 	int i = idque[first];
  19. 	first = first%(26*26) + 1;
  20. 	return i;
  21. }
  22.  
  23. int qput(int i){
  24. 	idque[last] = i;
  25. 	last = last%(26*26) + 1;
  26. }
  27.  
  28. int qinit(){
  29. 	first = 0;
  30. 	last = 0;
  31. }
  32.  
  33. // traceback
  34. int traceback[26*26] = {0};
  35.  
  36. // city name -> id
  37. int getid(char* city){
  38. 	return (city[0] - 65)*26 + city[1] - 65;
  39. }
  40.  
  41. // id -> city name
  42. int getname(int id, char* s){
  43. 	s[0] = id/26 + 65;
  44. 	s[1] = id%26 + 65;
  45. 	s[3] = 0;
  46. }
  47.  
  48. int main(){
  49. 	// this subject take multi data
  50. 	int data = 0;
  51. 	int n;
  52. 	while(1){
  53. 		// EOF
  54. 		if(scanf(" %d", &n) == EOF)
  55. 			break;
  56.  
  57. 		// blank line between multidata
  58. 		if(data > 0)
  59. 			printf("\n");
  60. 		data++;
  61.  
  62. 		// there are bridges between cities
  63. 		char bridge[26*26][26*26] = {0};
  64. 		char city1[3];
  65. 		char city2[3];	
  66. 		for(int i=0; i<n; i++){
  67. 			scanf(" %s %s", city1, city2);
  68. 			int id1 = getid(city1);
  69. 			int id2 = getid(city2);
  70. 			bridge[id1][id2] = 1;
  71. 			bridge[id2][id1] = 1;
  72. 		}
  73.  
  74. 		// get target
  75. 		char target1[3];
  76. 		char target2[3];
  77. 		scanf(" %s %s", target1, target2);
  78. 		int tid1 = getid(target1);
  79. 		int tid2 = getid(target2);
  80.  
  81. 		// put first item into que. the map m note which id was searched.
  82. 		qinit();
  83. 		char m[26*26] = {0};
  84. 		m[tid1] = 1;
  85. 		qput(tid1);
  86.  
  87. 		// start BFS
  88. 		char foundedflag = 0;
  89. 		while(!qempty()){
  90. 			int id = qget();
  91.  
  92. 			// target match
  93. 			if(id == tid2){
  94. 				foundedflag = 1;
  95. 				break;
  96. 			}
  97.  
  98. 			// search bridges
  99. 			for(int i=0; i<26*26; i++){
  100. 				// don't put searched item into que
  101. 				if(bridge[id][i] && !m[i]){
  102. 					m[i] = 1;
  103. 					qput(i);
  104. 					traceback[i] = id;
  105. 				}
  106. 			}
  107. 		}
  108.  
  109. 		// founded match, start traceback
  110. 		if(foundedflag){
  111. 			int cities[26*26] = {0};
  112. 			int len = 0;
  113. 			int id = tid2;
  114. 			while(1){
  115. 				cities[len] = id;
  116. 				len++;
  117. 				if(tid1 == id)
  118. 					break;
  119. 				id = traceback[id];
  120. 			}
  121. 			char s1[3] = {0};
  122. 			char s2[3] = {0};
  123. 			for(int i=len-1; i>0; i--){
  124. 				getname(cities[i], s1);
  125. 				getname(cities[i-1], s2);
  126. 				printf("%s %s\n", s1, s2);
  127. 			}
  128. 		}else{
  129. 			printf("No route\n");
  130. 		}
  131. 	}
  132. 	return 0;
  133. }
  134.  
Success #stdin #stdout 0s 3676KB
comments (?)
stdin
copy 
3
JV PT
KA PT
KA HP
JV HP

2
JV PT
KA HP
JV HP

4
PT HP
KA PT
KA HP
JV PT
HP JV
stdout
copy 
JV PT
PT KA
KA HP

No route

HP PT
PT JV
https://ideone.com/mjdUvM
language:
C++14 (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!