fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #define ll long long
  4. using namespace std;
  5. const int maxn = 20;
  6. const int oo = 1000000007;
  7. int n,m,h;
  8. int mat[maxn][maxn],dp[1<<maxn][maxn][maxn];
  9.  
  10. void enter()
  11. {
  12. 	int u,v,t;
  13. 	for (int i=0; i<=n-1; i++)
  14. 		for (int j=0; j<=n-1; j++)
  15. 			if (i!=j)
  16. 				mat[i][j]=oo;
  17. 			else mat[i][j]=0;
  18. 	for (int i=0; i<=1<<n; i++)
  19. 		for (int j=0; j<=n-1; j++)
  20. 			for (int z=0; z<=n-1; z++)
  21. 				dp[i][j][z]=oo;
  22. 	for (int i=1; i<=m; i++)
  23. 	{
  24. 		cin >> u >> v >> t;
  25. 		mat[u][v]=min(mat[u][v],t);
  26. 		mat[v][u]=min(mat[v][u],t);
  27. 	}
  28. 	//cout << mat[3][4] << '\n';
  29. }
  30. void floyd()
  31. {
  32. 	for (int x=0; x<=n-1; x++)
  33. 		for (int y=0; y<=n-1; y++)
  34. 			for (int z=0; z<=n-1; z++)
  35. 				mat[y][z]=min(mat[y][z],mat[y][x]+mat[x][z]);
  36. }
  37. int getbit(int x, int i)
  38. {
  39. 	return (x >> i) & 1;
  40. }
  41. int countone(int x)
  42. {
  43. 	int res=0;
  44. 	for (int i=0; i<=n-1; i++)
  45. 		if (getbit(x,i)==1) res++;
  46. 	return res;
  47. }
  48. // tra ve bit thu i cua so x
  49. int clearbit(int x, int i)
  50. {
  51. 	return x & (~(1 << i));
  52. } 
  53. int toggle(int x, int i)
  54. {
  55. 	int number=x;
  56. 	number ^= 1 << i;
  57. 	return number;
  58. }
  59. int caldp(int mask, int u, int v)
  60. {
  61. 	//cout << mask << ' ' << u << ' ' << v << '\n';
  62. 	if (dp[mask][u][v]==oo)
  63. 	{
  64. 		if (countone(mask)==0) dp[mask][u][v]=mat[u][v];
  65. 		else
  66. 		{
  67. 			for (int i=0; i<=n-1; i++)
  68. 				if (getbit(mask,i)==1)
  69. 					dp[mask][u][v]=min(dp[mask][u][v],caldp(clearbit(mask,i),u,i)+mat[i][v]);
  70. 		}
  71. 	}
  72. 	//cout << getbit(mask,n-2) << ' ';
  73. 	//for (int i=0; i<=n-1; i++)
  74. 	//	cout << getbit(mask,i);
  75. 	//cout << ' ' << getbit(mask,u) << ' ' << u << ' ' << v << ' ' << dp[mask][u][v] << '\n';
  76. 	return dp[mask][u][v];
  77. }
  78. int no(int x)
  79. {
  80. 	int xx=x;
  81. 	for (int i=0; i<=n-1; i++)
  82. 		xx=toggle(xx,i);
  83. 	return xx;	
  84. }
  85. void printbit(int x)
  86. {
  87. 	for (int i=0; i<=n-1; i++)
  88. 		cout << getbit(x,i);
  89. 	cout << ' ';
  90. }
  91. void solve(int t)
  92. {
  93. 	int res=oo;
  94. 	h=n-2;
  95. 	//printbit(16);
  96. 	//printbit(no(16));
  97. 	//cout << '\n';
  98. 	for (int i=0; i<=1<<(n-1); i++)
  99. 		if ((countone(i)==h/2) and (getbit(i,0)!=1) and (getbit(i,n-1)!=1))
  100. 		{
  101. 			int res1=oo,res2=oo,res3=oo,res4=oo;
  102. 			for (int j=1; j<=n-2; j++)
  103. 				if (getbit(i,j)==1)
  104. 				{
  105. 					int mask=clearbit(i,j);
  106. 					int mas=clearbit(clearbit(clearbit(no(i),n-1),0),j);
  107. 					//cout << getbit(mas,j) << '\n';
  108. 					//printbit(mask);
  109. 					//printbit(mas);
  110. 					//cout << '\n';
  111. 					res1=min(res1,caldp(mask,0,j)+caldp(mas,n-1,j));
  112. 				}
  113. 			for (int j=1; j<=n-2; j++)
  114. 				if (getbit(i,j)==1)
  115. 				{
  116. 					int mask=clearbit(i,j);
  117. 					int mas=clearbit(clearbit(clearbit(no(i),n-1),0),j);
  118. 					//cout << getbit(mas,j)<< '\n';
  119. 					//printbit(mask);
  120. 					//printbit(mas);
  121. 					//cout << '\n';
  122. 					res2=min(res2,caldp(mask,n-1,j)+caldp(mas,0,j));
  123. 				}
  124. 			//cout << res1 << ' ' << res2 << '\n';
  125. 			res=min(res,res1+res2);				
  126. 		}
  127. 	if (n==3) res=(mat[0][1]+mat[1][2])*2;
  128. 	cout << "Case " << t << ": " << res << '\n';
  129. }
  130. int main()
  131. {
  132. 	ios_base::sync_with_stdio(0);
  133. 	//freopen("1281.INP","r",stdin);
  134. 	//freopen("1281.OUT","w",stdout);
  135. 	int dem=0;
  136. 	while (cin >> n >> m)
  137. 	{
  138. 		dem++;
  139. 		enter();
  140. 		floyd();
  141. 		solve(dem);
  142. 		//cout << "OK\n";
  143. 	}
  144. 	return 0;
  145. }
  146.  
Runtime error #stdin #stdout 0s 144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kj4naT
language:
C++14 (gcc 8.3)
created:
9 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!