fork download
copy 
  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, int dist)
  10. {
  11. 	if(hascal[x][y][mask])
  12. 	{
  13. 		return dp[x][y][mask];
  14. 	}
  15. 	if(mask==0)
  16. 	{
  17. 		return dist;
  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. 				mn=min(mn,solve(target,y,mask ^ (1<<temp),dist+adj[x][target]));
  30. 				mn=min(mn,solve(x,target,mask ^ (1<<temp),dist+adj[y][target]));
  31. 			}
  32. 		}
  33. 		dp[x][y][mask]=mn;
  34. 		return mn;
  35.  
  36. 	}
  37. }
  38.  
  39. int main()
  40. {
  41. 	int temp,temp2,temp3,INF=10e8;
  42. 	for(temp=0;temp<=100;temp++)
  43. 	{
  44. 		for(temp2=0;temp2<=100;temp2++)
  45. 		{
  46. 			if(temp==temp2)
  47. 				adj[temp][temp2]=0;
  48. 			else
  49. 				adj[temp][temp2]=INF;
  50. 		}
  51. 	}
  52. 	int m,n;
  53. 	scanf("%d %d",&m,&n);
  54. 	for(temp=0;temp<n;temp++)
  55. 	{
  56. 		int a,b,c;
  57. 		scanf("%d %d %d",&a,&b,&c);
  58. 		adj[a][b]=adj[b][a]=min(adj[a][b],c);
  59. 	}
  60.  
  61. 	for(temp3=0;temp3<m;temp3++)
  62. 	{
  63. 		for(temp=0;temp<m;temp++)
  64. 		{
  65. 			for(temp2=0;temp2<m;temp2++)
  66. 			{
  67. 				adj[temp2][temp]=min(adj[temp][temp2],adj[temp][temp3]+adj[temp3][temp2]);
  68. 			}
  69. 		}
  70. 	}
  71.  
  72. 	scanf("%d",&ss);
  73. 	for(temp=0;temp<ss;temp++)
  74. 	{
  75. 		scanf("%d",&s[temp]);
  76. 	}
  77. 	int x,y;
  78. 	scanf("%d %d",&x,&y);
  79. 	int ans=solve(x,y,pow(2,ss)-1,0);
  80. 	printf("%d\n",ans);
  81. }
Success #stdin #stdout 0s 15624KB
comments (?)
stdin
copy 
5 6 
0 1 5 
0 2 2 
0 4 10 
1 3 5 
1 2 3 
1 4 10 
3 
2 4 3 
0 1
stdout
copy 
19
https://ideone.com/H30OGG
language:
C++ 4.3.2 (gcc-4.3.2)
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!