fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. #include <assert.h>
  5. #define hash 1024
  6.  
  7. int cityEdge[1004][5] = {};
  8. int shortPath[10][2000][1004] = {}, pathNum;
  9. int visited[1004] = {};
  10. int storeEdge[20000] = {};
  11. int queue[1004] = {}, head, tail, edgeNum;
  12. int stack[1004] = {}, top;
  13. int outputStack[1004] = {}, con, endss;
  14.  
  15. void outputstack(int station, int pos){
  16. 	if(station == con - 1){
  17. 		for(int i = 0; i < pos; i++){
  18. 			printf("%d ", outputStack[i]);
  19. 		}
  20. 		printf("%d\n", endss);
  21. 	}else{
  22. 		for(int i = 1; i <= shortPath[station][0][0]; i++){
  23. 			for(int j = 1; j <= shortPath[station][0][1] + 1; j++){
  24. 				outputStack[pos+j-1] = shortPath[station][i][j];
  25. 			}
  26. 			outputstack(station + 1, pos + shortPath[station][0][1]);
  27. 		}
  28. 	}
  29.  
  30. }
  31.  
  32. using namespace std;
  33.  
  34. int cmp(const void *a, const void *b){
  35. 	int* aa = (int*)a;
  36. 	int* bb = (int*)b;
  37. 	if(*aa > *bb) return 1;
  38. 	else return -1;
  39. }
  40.  
  41. int cmp2(const void *a, const void *b){
  42. 	int *aa = (int *)a;
  43. 	int *bb = (int *)b;
  44. 	for(int i = 1; ;i ++){
  45. 		if(aa[i] > bb[i]) return 1;
  46. 		if(aa[i] < bb[i]) return -1;
  47. 	}
  48. }
  49.  
  50.  
  51. void DFS(int end, int station, int depth){
  52. 	stack[top++] = end;
  53. 	if(depth > 0){
  54. 		int low = lower_bound(storeEdge, storeEdge+edgeNum, end * hash) - storeEdge;
  55. 		int upp = upper_bound(storeEdge, storeEdge+edgeNum, (end+1) * hash) - storeEdge;
  56. 		for(int i = low; i < upp; i++){
  57. 			DFS(storeEdge[i] % hash, station, depth - 1);
  58. 		}
  59. 		top--;
  60. 	}else{
  61. 		pathNum ++;
  62. 		for(int i = 0; i < top; i++){
  63. 			shortPath[station][pathNum][top-i] = stack[i];
  64. 		}
  65. 		top--;
  66. 		return;
  67. 	}
  68.  
  69. }
  70.  
  71. void BFS(int start, int end, int station){
  72. 	memset(visited, -1, sizeof(int) * 1004);
  73. 	memset(storeEdge, 0, sizeof(int) * 20000);
  74. 	head = edgeNum = 0;
  75. 	tail = 1;
  76. 	queue[0] = start, visited[start] = 0;
  77. 	while(head != tail && visited[end] == -1){
  78. 		int tmp = queue[head++];
  79. 		for(int i = 1; i <= cityEdge[tmp][0]; i++){
  80. 			if(visited[cityEdge[tmp][i]] != -1){
  81. 				if(visited[cityEdge[tmp][i]] == visited[tmp] + 1)
  82. 					storeEdge[edgeNum++] = cityEdge[tmp][i] * hash + tmp;
  83. 				continue;
  84. 			}
  85. 			visited[cityEdge[tmp][i]] = visited[tmp] + 1;
  86. 			storeEdge[edgeNum++] = cityEdge[tmp][i] * hash + tmp;
  87. 			queue[tail++] = cityEdge[tmp][i];
  88. 		}
  89. 	}
  90. 	assert(head!=tail);
  91. 	int tmp = queue[head++];
  92. 	while(visited[end] == visited[tmp] + 1){
  93. 		for(int i = 1; i <= cityEdge[tmp][0]; i++){
  94. 			if(cityEdge[tmp][i] == end){
  95. 				storeEdge[edgeNum++] = cityEdge[tmp][i] * hash + tmp;
  96. 			}
  97. 		}
  98. 		if(head == tail) break; 
  99. 		tmp = queue[head++];
  100. 	}
  101.  
  102.  
  103. 	qsort(storeEdge, edgeNum, sizeof(int), cmp);
  104.  
  105. 	memset(stack, 0, sizeof(int) * 1004);
  106. 	top = 0, pathNum = 0;
  107. 	DFS(end, station, visited[end]);
  108. 	shortPath[station][0][0] = pathNum;
  109. 	shortPath[station][0][1] = visited[end];
  110. 	for(int i = 1; i <= pathNum; i++){
  111. 		qsort(&shortPath[station][1], pathNum, sizeof(int)*1004, cmp2);
  112. 	}
  113. }
  114.  
  115. int main(){
  116.  
  117. 	int cityNum, nightNum;
  118. 	scanf("%d %d", &cityNum, &nightNum);
  119. 	for(int i = 1; i <= cityNum; i++){
  120. 		int city, tmp, connected = 0;
  121. 		char ch;
  122. 		scanf("%d", &tmp);
  123. 		while(scanf("%d%c", &city, &ch) != EOF){
  124.     		cityEdge[tmp][++connected] = city;
  125. 			if(ch == '\n') break;
  126. 		}
  127. 		cityEdge[tmp][0] = connected;
  128. 		qsort(cityEdge[tmp] + 1, connected, sizeof(int), cmp);
  129. 	}
  130.  
  131. 	for(int i = 1; i <= nightNum; i++){
  132. 		memset(shortPath, 0, sizeof(int) * 10 * 500 * 1004);
  133. 		printf("Night %d:\n", i);
  134. 		int cityConnected[10];
  135. 		int city, connected = 0;
  136. 		char ch;
  137. 		while(scanf("%d%c", &city, &ch) != EOF){
  138.     		cityConnected[++connected] = city;
  139. 			if(ch == '\n') break;
  140. 		}
  141.  
  142. 		for(int i = 1; i < connected; i++){
  143. 			//printf("%d %d:\n", cityConnected[i], cityConnected[i+1]);
  144. 			BFS(cityConnected[i], cityConnected[i+1], i-1);
  145. 		}
  146.  
  147. 		int len = 0;
  148. 		int path = 1;
  149.  
  150. 		for(int i = 1; i < connected; i++){
  151. 			path *= shortPath[i-1][0][0];
  152. 			len += shortPath[i-1][0][1];
  153. 		}
  154. 		printf("Possible ways: %d\nNumber of stations: %d\n", path, len + 1);
  155. 		puts("Path:");
  156. 		con = connected;
  157. 		endss = cityConnected[connected];
  158. 		memset(outputStack, 0, sizeof(int) * 1004);
  159. 		outputStack[0] = cityConnected[1];
  160. 		outputstack(0, 0);
  161. 		puts("");
  162. 	}
  163. }
Success #stdin #stdout 0s 93760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7uKORQ
language:
C++ (gcc 8.3)
created:
6 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!