fork download
copy 
  1. //208 Firetruck
  2. //https://u...content-available-to-author-only...e.org/external/2/208.pdf
  3.  
  4. #define _CRT_SECURE_NO_WARNINGS
  5.  
  6. #include<stdio.h>
  7.  
  8. #define MAX 22
  9. #define MAXNODE 100
  10. #define INFINITY 32767
  11.  
  12. int addj[MAXNODE][MAXNODE];
  13. int visited[MAXNODE][MAXNODE];
  14. int path[1000];
  15. int trout = 0;
  16. int vist[MAXNODE];
  17. int dist[MAXNODE][MAXNODE];
  18. void init()
  19. {
  20. 	for (int i = 0; i <= MAXNODE; i++)
  21. 	{
  22. 		path[i] = 0;
  23. 		vist[i] = 0;
  24. 		for (int j = 0; j <= MAXNODE; j++)
  25. 		{
  26. 			addj[i][j] = visited[i][j] = 0;
  27. 			dist[i][j] = INFINITY;
  28. 		}
  29.  
  30. 	}
  31. }
  32.  
  33. void foloyd_warshal(int maxnode)
  34. {
  35. 	for (int i = 0; i <= maxnode; i++)
  36. 	{
  37. 		dist[i][i] = 0;
  38. 	}
  39.  
  40. 	for (int k = 0; k <= maxnode; k++)
  41. 	{
  42. 		for (int i = 0; i <= maxnode; i++)
  43. 		{
  44. 			for (int j = 0; j <= maxnode; j++)
  45. 			{
  46. 				if (dist[i][j] > dist[i][k] + dist[k][j])
  47. 				{
  48. 					dist[i][j] = dist[i][k] + dist[k][j];
  49. 				}
  50. 			}
  51.  
  52. 		}
  53. 	}
  54. }
  55.  
  56.  
  57.  
  58.  
  59. void find_rout(int node,int firecorner,int maxnode,int index)
  60. {
  61. 	int np = 0;
  62. 	if (node == firecorner)
  63. 	{
  64. 		//printf("   ");
  65. 		int i = 0;
  66. 		for (i = 0; i < index-1; i++)
  67. 			printf("%d ",path[i]);
  68. 		printf("%d", path[i]);
  69. 		printf("\n");
  70. 		trout++;
  71. 		return ;
  72. 	}
  73. 	for (int v = 0; v <= maxnode; v++)
  74. 	{
  75. 		if (((addj[node][v]) && (!vist[v])) && (dist[firecorner][v]<INFINITY))
  76. 		{
  77. 			visited[node][v] = 1;
  78. 			path[index] = v;
  79. 			np = v;
  80. 			vist[v] = 1;
  81. 			find_rout(np, firecorner, maxnode, index + 1);
  82. 			vist[np] = 0;
  83. 			/*if (np>2)
  84. 				vist[np] = 0;*/
  85. 		}
  86. 	}
  87. }
  88.  
  89. int main()
  90. {
  91. 	int firecorner = 0,case1=1;
  92. 	int u, v,maxnode;
  93. 	/*freopen("in.txt","r",stdin);
  94. 	freopen("out.txt","w",stdout);*/
  95.  
  96. 	while (scanf("%d", &firecorner) != EOF)
  97. 	{
  98. 		maxnode = 0;
  99. 		trout = 0;
  100. 		init();
  101. 		while (1)
  102. 		{
  103. 			scanf("%d %d", &u, &v);
  104. 			if (u == 0 && v == 0)
  105. 				break;
  106. 			addj[u][v] = 1;
  107. 			addj[v][u] = 1;
  108. 			dist[u][v] = 1;
  109. 			dist[v][u] = 1;
  110. 			if (maxnode < u)
  111. 				maxnode = u;
  112. 			if (maxnode < v)
  113. 				maxnode = v;
  114. 		}
  115. 		foloyd_warshal(maxnode);
  116. 		path[0] = 1;
  117. 		vist[1] = 1;
  118. 		printf("CASE %d:\n", case1++);
  119. 		find_rout(1, firecorner,maxnode,1);
  120. 		printf("There are %d routes from the firestation to streetcorner %d.\n", trout,firecorner);
  121. 	}
  122.  
  123. 	return 0;
  124. }
Success #stdin #stdout 0s 16184KB
comments (?)
stdin
copy 
6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
4
2 3
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0
stdout
copy 
CASE 1:
There are 32767 routes from the firestation to streetcorner 6.
CASE 2:
There are 32767 routes from the firestation to streetcorner 4.
https://ideone.com/AuwQb9
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!