fork download
copy 
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<stdlib.h>
  4.  
  5. struct tdata
  6. {
  7. 	int kota;
  8. 	int cost;
  9. 	struct tdata *next;
  10. };
  11.  
  12. struct heapData 
  13. {
  14. 	int distance;
  15. 	int kota;
  16. };
  17.  
  18. heapData arrHeap[100000000];
  19. int heapCountData = 0;
  20.  
  21. struct tdata *adjListHead[100000000];
  22.  
  23. int compare(struct heapData a, struct heapData b)
  24. {
  25. 	if(a.distance < b.distance)
  26. 	{
  27. 		return -1;
  28. 	}
  29. 	if(a.distance==b.distance)
  30. 	{
  31. 		if(a.kota < b.kota)
  32. 		{
  33. 			return -1;
  34. 		}
  35. 		if(a.kota==b.kota)
  36. 		{
  37. 			return 0;
  38. 		}
  39. 		return 1;
  40. 	}
  41. 	return 1;
  42. }
  43.  
  44. void downHeap(struct heapData *heapArr,int idx,int ndata)
  45. {
  46. 	int toIdx = idx;
  47.  
  48. 	if(2*idx <= ndata && compare(heapArr[toIdx],heapArr[2*idx])>0)
  49. 	{
  50. 		toIdx = 2*idx;
  51. 	}
  52. 	if(2*idx+1 <=ndata &&compare(heapArr[toIdx],heapArr[2*idx+1])>0)
  53. 	{
  54. 		toIdx = 2*idx+1;
  55. 	}
  56. 	if(toIdx==idx)
  57. 	{
  58. 		return;
  59. 	}
  60.  
  61. 	struct heapData temp = heapArr[toIdx];
  62. 	heapArr[toIdx] = heapArr[idx];
  63. 	heapArr[idx] = temp;
  64.  
  65. 	downHeap(heapArr,toIdx,ndata);
  66. }
  67.  
  68. void popHeap(struct heapData *heapArr, int *n)
  69. {
  70. 	if(*n==1)
  71. 	{
  72. 		(*n)--;
  73. 		return;
  74. 	}
  75.  
  76. 	heapArr[1] = heapArr[*n];
  77. 	(*n)--;
  78. 	downHeap(heapArr,1,*n);
  79. }
  80.  
  81. void upHeap(struct heapData *heapArr, int idx, int ndata)
  82. {
  83. 	if(idx==1)
  84. 	{
  85. 		return;
  86. 	}
  87. 	int ParentIdx = idx/2;
  88.  
  89. 	if(compare(heapArr[ParentIdx],heapArr[idx])<0)
  90. 	{
  91. 		return;
  92. 	}
  93.  
  94. 	struct heapData temp = heapArr[ParentIdx];
  95. 	heapArr[ParentIdx] = heapArr[idx];
  96. 	heapArr[idx] = temp;
  97.  
  98. 	upHeap(heapArr, ParentIdx,ndata);
  99. }
  100.  
  101. void pushHeap(struct heapData *heapArr,int *n,int distance,int kota)
  102. {
  103. 	(*n)++;
  104. 	heapArr[*n].distance = distance;
  105. 	heapArr[*n].kota = kota;
  106. 	upHeap(heapArr,*n,*n);
  107. }
  108.  
  109. void pushList(struct tdata **localHead,int kota,int cost)
  110. {
  111. 	struct tdata *newnode = (struct tdata*)malloc(sizeof(struct tdata));
  112. 	newnode->next = NULL;
  113. 	newnode->kota = kota;
  114. 	newnode->cost = cost;
  115.  
  116. 	if(*localHead == NULL)
  117. 	{
  118. 		*localHead = newnode;
  119. 	}
  120. 	else
  121. 	{
  122. 		newnode->next = *localHead;
  123. 		*localHead = newnode;
  124. 	}
  125. }
  126.  
  127. void popAll(struct tdata **localHead)
  128. {
  129. 	while(*localHead != NULL)
  130. 	{
  131. 		struct tdata *del = *localHead;
  132. 		*localHead = (*localHead)->next;
  133. 		free(del);
  134. 	}
  135. }
  136.  
  137. int visited[100010];
  138. int distance[100010];
  139.  
  140. int dijkstra(struct tdata **localAdjList,int V,int a,int b)
  141. {
  142. 	heapCountData = 0;
  143. 	for(int i=0;i<=V;i++)
  144. 	{
  145. 		visited[i] = 0;
  146. 		distance[i] = (1<<30);
  147. 	}
  148.  
  149. 	distance[a] = 0;
  150.  
  151. 	pushHeap(arrHeap,&heapCountData,distance[a],a);
  152.  
  153. 	while(heapCountData > 0)
  154. 	{	
  155. 		int curKota = arrHeap[1].kota;
  156. 		int curDist = arrHeap[1].distance;
  157. //		printf("%d %d\n",curKota,curDist);
  158. 		popHeap(arrHeap,&heapCountData);
  159. 		if(visited[curKota])
  160. 		{
  161. 			continue;
  162. 		}
  163.  
  164. 		visited[curKota] = 1;
  165.  
  166. 		if(curKota==b)
  167. 		{
  168. 			return distance[b];
  169. 		}
  170.  
  171. 		struct tdata *current = localAdjList[curKota];
  172.  
  173. 		while(current!=NULL)
  174. 		{
  175. 			if(visited[current->kota]==0 && (distance[curKota]+current->cost) < distance[current->kota])
  176. 			{
  177. 				distance[current->kota] = distance[curKota] + current->cost;
  178. 				pushHeap(arrHeap,&heapCountData,distance[current->kota],current->kota);
  179. 			}
  180. 			current = current->next;
  181. 		}
  182. 	}
  183.  
  184. 	return distance[b];
  185. }
  186.  
  187. int main()
  188. {
  189. 	int tc;
  190. 	scanf("%d",&tc);
  191. 	for(int i=1;i<=tc;i++)
  192. 	{
  193. 		int n;
  194. 		int m;
  195. 		int S;
  196. 		int T;
  197.  
  198. 		scanf("%d %d %d %d",&n,&m,&S,&T);
  199.  
  200. 		for(int j=0;j<m;j++)
  201. 		{
  202. 			int a;
  203. 			int b;
  204. 			int cost;
  205. 			scanf("%d %d %d",&a,&b,&cost);
  206. 			pushList(&adjListHead[a],b,cost);
  207. 			pushList(&adjListHead[b],a,cost);
  208. 		}
  209.  
  210. 		int ans = dijkstra(adjListHead,n,S,T);
  211. 		if(visited[T])
  212. 		{
  213. 			printf("Case #%d: %d\n",i,ans);	
  214. 		}
  215. 		else
  216. 		{
  217. 			printf("Case #%d: unreachable",i);
  218. 		}
  219.  
  220. 		for(int i=0; i<n; i++) 
  221. 		{
  222. 			popAll(&adjListHead[i]);
  223. 		}
  224. 	}
  225.  
  226. 	return 0;
  227. }
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
1
5 4 2
2 4
1 2
2 3
3 4
4 5
stdout
copy 
Case #1: 0
https://ideone.com/xADJxx
language:
C++ (gcc 8.3)
created:
4 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!