fork(2) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int adj[101][101];
  5. int dp[101][101][258];
  6. bool hascal[101][101][258];
  7. int s[8],ss;
  8.  
  9. int solve(int x,int y, int mask)
  10. {
  11. 	if(hascal[x][y][mask])
  12. 	{
  13. 		return dp[x][y][mask];
  14. 	}
  15. 	if(mask==0)
  16. 	{
  17. 		return 0; ///Return 0 if we're done since there's nothing else to do
  18. 	}
  19. 	else
  20. 	{
  21. 		hascal[x][y][mask]=true;
  22. 		int temp;
  23. 		int mn=INT_MAX;
  24. 		for(temp=0;temp<ss;temp++)
  25. 		{
  26. 			if(mask & (1<<temp))
  27. 			{
  28. 				int target=s[temp];
  29.  
  30. 				mn=min(mn,solve(target,y,mask ^ (1<<temp))+adj[x][target]); ///The addition is outside of the solve function
  31. 				mn=min(mn,solve(x,target,mask ^ (1<<temp))+adj[y][target]); ///Since we move to that state at such cost
  32. 			}
  33. 		}
  34. 		dp[x][y][mask]=mn;
  35. 		return mn;
  36.  
  37. 	}
  38. }
  39.  
  40. int main()
  41. {
  42. 	int temp,temp2,temp3,INF=10e8;
  43. 	for(temp=0;temp<=100;temp++)
  44. 	{
  45. 		for(temp2=0;temp2<=100;temp2++)
  46. 		{
  47. 			if(temp==temp2)
  48. 				adj[temp][temp2]=0;
  49. 			else
  50. 				adj[temp][temp2]=INF;
  51. 		}
  52. 	}
  53. 	int m,n;
  54. 	scanf("%d %d",&m,&n);
  55. 	for(temp=0;temp<n;temp++)
  56. 	{
  57. 		int a,b,c;
  58. 		scanf("%d %d %d",&a,&b,&c);
  59. 		adj[a][b]=adj[b][a]=min(adj[a][b],c);
  60. 	}
  61.  
  62. 	for(temp3=0;temp3<m;temp3++)
  63. 	{
  64. 		for(temp=0;temp<m;temp++)
  65. 		{
  66. 			for(temp2=0;temp2<m;temp2++)
  67. 			{
  68. 				adj[temp2][temp]=min(adj[temp][temp2],adj[temp][temp3]+adj[temp3][temp2]);
  69. 			}
  70. 		}
  71. 	}
  72.  
  73. 	scanf("%d",&ss);
  74. 	for(temp=0;temp<ss;temp++)
  75. 	{
  76. 		scanf("%d",&s[temp]);
  77. 	}
  78. 	int x,y;
  79. 	scanf("%d %d",&x,&y);
  80. 	int ans=solve(x,y,pow(2,ss)-1);
  81.  
  82. 	printf("%d\n",ans);
  83. }
  84.  
Success #stdin #stdout 0s 16352KB
comments (?)
stdin 
5 6
0 1 5
1 4 1
0 4 10
0 2 2
1 2 3
2 3 4
2
2 4
0 1
stdout 
3
https://ideone.com/fohxZK
language:
C++14 (gcc 8.3)
created:
8 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!