fork download
copy 
  1. #include<stdio.h>
  2. #include<assert.h>
  3. #define min(a,b) (a<b)?a:b
  4. int heapsize=0,t[251][251],mindis[251],seen[251],s,g,d,m,n;
  5. typedef struct node{
  6. 	int vertex,length;
  7. }node;
  8. node heap[63000];
  9. void insert(node x)
  10. {
  11. 	heapsize++;
  12. 	heap[heapsize]=x;
  13. 	int now=heapsize,parent=heapsize/2;
  14. 	while(heap[parent].length>x.length&&parent>=1)
  15. 	{
  16. 		heap[now]=heap[parent];
  17. 		now/=2,parent/=2;
  18. 	}
  19. 	heap[now]=x;
  20. }
  21. void delete_min()
  22. {
  23. 	node temp=heap[heapsize--];
  24. 	heap[1]=temp;
  25. 	int now=1,leftchild=2,rightchild=3;
  26. 	while(1)
  27. 	{
  28. 		leftchild=2*now,rightchild=2*now+1;
  29. 		if(leftchild>heapsize)
  30. 		break;
  31. 		if(heap[now].length>heap[leftchild].length)
  32. 		{
  33. 			heap[now]=heap[leftchild];
  34. 			heap[leftchild]=temp;
  35. 			now=leftchild;
  36. 			continue;
  37. 		}
  38. 		if(rightchild>heapsize)
  39. 		{
  40. 			break;
  41. 		}
  42. 		if(heap[leftchild].length>=heap[now].length&&heap[rightchild].length>=heap[now].length)
  43. 		{
  44. 			break;
  45. 		}
  46. 		if(heap[now].length>heap[rightchild].length)
  47. 		{
  48. 			heap[now]=heap[rightchild];
  49. 			heap[rightchild]=temp;
  50. 			now=rightchild;
  51. 			continue;
  52. 		}
  53. 	}
  54. }
  55. void shortest(int st)
  56. {
  57. 	int i,presentvertex;
  58. 	heapsize=0;
  59. 	node temp,min;
  60. 	for( i=1;i<=n;i++)
  61. 	{
  62. 		if(i==st)
  63. 		{
  64. 			mindis[i]=0;
  65. 			seen[i]=1;
  66. 		}
  67. 		else
  68. 		{
  69. 			mindis[i]=t[st][i];
  70. 			temp.vertex=i;
  71. 			temp.length=t[st][i];
  72. 			insert(temp);
  73. 			seen[i]=0;
  74. 		}
  75. 	}
  76. 	while(heapsize>0)
  77. 	{
  78. 		min=heap[1];
  79. 		delete_min();
  80. 		//for(i=1;i<=heapsize;i++)
  81. 		//printf("Vertex:%d  Distance:%d ",heap[i].vertex,heap[i].length);
  82. 		//printf("\n");
  83. 		presentvertex=min.vertex;
  84. 		if(seen[presentvertex])
  85. 		{
  86. 			continue;
  87. 		}
  88. 		seen[presentvertex]=1;
  89. 		for(i=1;i<=heapsize;i++)
  90. 		{
  91. 			if(seen[i])
  92. 			continue;
  93. 			if(mindis[i]>t[presentvertex][i]+mindis[presentvertex])
  94. 			{	
  95. 				mindis[i]=t[presentvertex][i]+mindis[presentvertex];
  96. 				temp.vertex=i;
  97. 				temp.length=mindis[i];
  98. 				insert(temp);
  99. 			}
  100. 		}
  101. 	}
  102. }
  103. int main()
  104. {
  105. 	int i,j,a,b,c;
  106. 	scanf("%d",&n);
  107. 	for(i=1;i<=n;i++)
  108. 	{	
  109. 		for(j=1;j<=n;j++)
  110. 		{
  111. 			scanf("%d",&t[i][j]);
  112. 		}
  113. 	}
  114. 	scanf("%d",&m);
  115.  
  116. 	while(m--)
  117. 	{
  118. 		scanf("%d%d%d",&s,&g,&d);
  119. 		s++,g++,d++;
  120. 		shortest(s);
  121. 		a=mindis[g];b=mindis[d];
  122. 		shortest(g);
  123. 		c=mindis[d];
  124. 		printf("%d %d\n",a+c,a+c-b);
  125. 	}
  126. 	return 0;
  127. }
Success #stdin #stdout 0.01s 3424KB
comments (?)
stdin
copy 
4
0 2 1 3
1 0 4 5
3 1 0 3
1 1 1 0
4
0 2 1
0 2 2
3 1 2
3 0 1
stdout
copy 
2 0
1 0
5 4
3 2
https://ideone.com/CTSyW
language:
C++ (gcc 8.3)
created:
12 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!