fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  5. #define chmin(X,Y) X=min(X,Y)
  6. #define N 15
  7. #define F 4
  8. int m[N], f[N];
  9. int g[N][N][N][N];
  10. int ld[N][F][N][1<<N], gd[N][1<<N];
  11. int c1[N], c2[N], sf, n, fr, fp[N];
  12. int d4[N][F][F];
  13. bool ng;
  14.  
  15. int INF = 151587081;
  16.  
  17. void ltsp(int cr, int ct){
  18. 	ld[cr][ct][ct][1<<ct] = 0;
  19. 	int mm = m[cr];
  20. 	for(int i = 0; i < 1<<mm; i++){
  21. 		if(!(1&(i>>ct))) continue;
  22. 		for(int j = 0; j < mm; j++){
  23. 			if(ld[cr][ct][j][i]>=INF) continue;
  24. 			for(int k = 0; k < mm; k++){
  25. 				if(1&(i>>k)) continue;
  26. 				chmin(ld[cr][ct][k][i|(1<<k)], ld[cr][ct][j][i]+g[cr][j][cr][k]);
  27. 			}
  28. 		}
  29. 	}
  30. }
  31.  
  32. void pre_calc(int cr){
  33. 	if(f[cr] == m[cr]) return;
  34. 	if(f[cr] == 1){
  35. 		ng = true;
  36. 	} else if(f[cr] == 4) {
  37. 		for(int i = 0; i < 4; i++){
  38. 			for(int j = i+1; j < 4; j++){
  39. 				int k = 0;
  40. 				while(k==i||k==j) k++;
  41. 				int l = k+1;
  42. 				while(l==i||l==j) l++;
  43. 				for(int b = (1<<i)|(1<<j); b < 1<<m[cr]; b+=1<<4)
  44. 					chmin(d4[cr][i][j], ld[cr][i][j][b]+ld[cr][k][l][(1<<m[cr])-b-1]);
  45. 			}
  46. 		}
  47. 	}
  48. }
  49.  
  50. int gtsp(int st, int start){
  51. 	memset(gd, 9, sizeof(gd));
  52. 	gd[start][0] = 0;
  53. 	for(int i = 0; i < 1<<sf; i++){
  54. 		for(int j = 0; j < sf; j++){
  55. 			if(gd[j][i]>=INF) continue;
  56. 			int f1 = c1[j], f2 = c2[j];
  57. 			for(int k = 0; k < sf; k++){
  58. 				if((1&(i>>k))) continue;
  59. 				int t1 = c1[k], t2 = c2[k];
  60. 				int kk = k-t2;
  61. 				int sz = f[t1];
  62. 				int r = gd[j][i]+g[f1][f2][t1][t2];
  63. 				if(r>=INF) continue; 
  64. 				if(f[t1]==m[t1]){
  65. 					chmin(gd[k][i|(1<<k)], r);
  66. 				} else if(f[t1]==2){
  67. 					int k2 = kk+1-t2;
  68. 					chmin(gd[k2][i|(1<<k)|(1<<k2)], r+ld[t1][0][1][(1<<m[t1])-1]);
  69. 				} else if(f[t1]==3){
  70. 					if(7&(i>>kk)){
  71. 						if(7&((i|(1<<k))>>kk)==7){
  72. 							chmin(gd[k][i|(1<<k)], r);
  73. 						} else {
  74. 							for(int k2 = kk; k2 < kk+3; k2++){
  75. 								if(k!=k2 && !(1&(i>>k2))){
  76. 									chmin(gd[k2][i|(1<<k)|(1<<k2)], r);
  77. 								}
  78. 							}
  79. 						}
  80. 					} else {
  81. 						for(int tt = 0; tt < 3; tt++){
  82. 							int k2 = kk+tt;
  83. 							if(k==k2) continue;
  84. 							int tt2 = 3-t2-tt;
  85. 							int k3 = kk+tt2;
  86. 							chmin(gd[k2][i|(1<<k)|(1<<k2)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt2)]);
  87. 							chmin(gd[k2][i|(1<<k)|(1<<k2)|(1<<k3)], r+ld[t1][t2][tt][(1<<m[t1])-1]);
  88. 							chmin(gd[k][i|(1<<k)], r+ld[t1][tt][tt2][((1<<m[t1])-1)^(1<<t2)]);
  89. 						}
  90. 					}
  91. 				} else {
  92. 					if(1&(st>>fp[t1])){
  93. 						if(15&(i>>kk)){
  94. 							for(int k2 = kk; k2 < kk+4; k2++){
  95. 								if(k2==k || (1&(i>>k2))) continue;
  96. 								chmin(gd[k2][i|(1<<k)|(1<<k2)], r);
  97. 							}
  98. 						} else {
  99. 							for(int tt = 0; tt < 4; tt++){
  100. 								if(tt==t2) continue;
  101. 								int k2 = kk+tt;
  102. 								for(int tt2 = 0; tt2 < 4; tt2++){
  103. 									if(tt2==t2 || tt2==tt) continue;
  104. 									int tt3 = 6-t2-tt-tt2;
  105. 									int k3 = kk+tt2, k4 = kk+tt3;
  106. 									chmin(gd[k2][i|(1<<k)|(1<<k2)], r+d4[t1][t2][tt]);
  107. 								}
  108. 							}
  109. 						}
  110. 					} else {
  111. 						if(__builtin_popcount(15&(i>>kk))==1){
  112. 							for(int tt = 0; tt < 4; tt++){
  113. 								int k2 = kk+tt;
  114. 								if(!(1&(i>>k2))) continue;
  115. 								for(int tt2 = 0; tt2 < 4; tt2++){
  116. 									if(tt2==t2 || tt2==tt) continue;
  117. 									int tt3 = 6-t2-tt-tt2;
  118. 									int k3 = kk+tt2, k4 = kk+tt3;
  119. 									chmin(gd[k2][i|(1<<k)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<t2)^(1<<tt)]);
  120. 									chmin(gd[k2][i|(1<<k)|(1<<k3)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt)^(1<<tt3)]);
  121. 									chmin(gd[k2][i|(1<<k)|(1<<k3)|(1<<k4)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt)]);
  122. 								}
  123. 							}
  124. 						} else if(15&(i>>kk)){
  125. 							chmin(gd[k][i|(1<<k)], r);
  126. 						} else {
  127. 							chmin(gd[k][i|(1<<k)], r);
  128. 							for(int tt = 0; tt < 4; tt++){
  129. 								if(tt==t2) continue;
  130. 								int k2 = kk+tt;
  131. 								for(int tt2 = 0; tt2 < 4; tt2++){
  132. 									if(tt2==t2 || tt2==tt) continue;
  133. 									int tt3 = 6-t2-tt-tt2;
  134. 									int k3 = kk+tt2, k4 = kk+tt3;
  135. 									chmin(gd[k2][i|(1<<k)|(1<<k2)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt2)^(1<<tt3)]);
  136. 									chmin(gd[k2][i|(1<<k)|(1<<k2)|(1<<k3)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt3)]);
  137. 									chmin(gd[k2][i|(1<<k)|(1<<k2)|(1<<k3)|(1<<k4)], r+ld[t1][t2][tt][((1<<m[t1])-1)]);
  138. 								}
  139. 							}
  140. 						}
  141. 					}
  142. 				}
  143. 			}
  144. 		}
  145. 	}
  146. 	return gd[start][(1<<sf)-1];
  147. }
  148.  
  149. int main(){
  150. 	memset(g, 9, sizeof(g));
  151. 	memset(ld, 9, sizeof(ld));
  152. 	memset(d4, 9, sizeof(d4));
  153. 	int K;
  154. 	cin>>n>>K;
  155. 	for(int i = 0; i < n; i++) cin>>m[i];
  156. 	for(int i = 0; i < n; i++){
  157. 		cin>>f[i];
  158. 		sf += f[i];
  159. 		if(f[i]==4){
  160. 			fp[i] = fr++;
  161. 		}
  162. 	}
  163. 	if(n==1){
  164. 		sf = m[0];
  165. 		for(int i = m[0]-1; i >= 0; i--)
  166. 			m[i] = f[i] = 1;
  167. 	}
  168. 	for(int i = 0; i < K; i++){
  169. 		int a, b, c, d, e;
  170. 		cin>>a>>b>>c>>d>>e;
  171. 		a--; b--; c--; d--;
  172. 		if(n==1) swap(a, b), swap(c, d);
  173. 		g[a][b][c][d] = g[c][d][a][b] = e;
  174. 	}
  175. 	if(n==1 && sf==1){
  176. 		cout<<0<<endl;
  177. 		return 0;
  178. 	}
  179. 	for(int i = 0, cc1 = 0, cc2 = 0; i < sf; i++){
  180. 		if(cc2>=f[cc1]){
  181. 			cc1++;
  182. 			cc2 = 0;
  183. 		}
  184. 		c1[i] = cc1;
  185. 		c2[i] = cc2++;
  186. 	}
  187. 	for(int i = 0; i < n; i++){
  188. 		for(int j = 0; j < f[i]; j++)
  189. 			ltsp(i, j);
  190. 		pre_calc(i);
  191. 	}
  192. 	if(ng){
  193. 		cout<<-1<<endl;
  194. 		return 0;
  195. 	}
  196. 	int res = INF;
  197. 	for(int i = 0; i < 1<<fr; i++)
  198. 		for(int j = 0; j < sf; j++)
  199. 			res = min(res, gtsp(i, j));
  200. 	cout<<(res==INF?-1:res)<<endl;
  201. 	return 0;
  202. }
  203.  
Success #stdin #stdout 0.12s 120768KB
comments (?)
stdin 
4 6
1 1 1 1
1 1 1 1
1 1 2 1 1
1 1 3 1 2
1 1 4 1 1
2 1 3 1 1
2 1 4 1 2
3 1 4 1 1
stdout 
4
https://ideone.com/gFCDZv
language:
C++ (gcc 8.3)
created:
8 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!