fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. #define chmin(X,Y) X=min(X,Y)
  7. #define N 15
  8. #define F 4
  9. int m[N], f[N];
  10. int g[N][N][N][N];
  11. int ld[N][F][N][1<<N], gd[N][1<<N];
  12. int c1[N], c2[N], sf, n;
  13. int d1[N], d2[N], d3a[N][F], d3b[N][F], d4a[N][F][F], d4b[N][F][F], d4c[N][F][F][F], d4d[N][F][F];
  14. int pat[N], u1[N], u2[N], u3[N];
  15.  
  16. bool ng;
  17.  
  18. int INF = 151587081;
  19.  
  20. void ltsp(int cr, int ct){
  21. 	ld[cr][ct][ct][1<<ct] = 0;
  22. 	int mm = m[cr];
  23. 	for(int i = 0; i < 1<<mm; i++){
  24. 		if(!(1&(i>>ct))) continue;
  25. 		for(int j = 0; j < mm; j++){
  26. 			if(ld[cr][ct][j][i]>=INF) continue;
  27. 			for(int k = 0; k < mm; k++){
  28. 				if(1&(i>>k)) continue;
  29. 				chmin(ld[cr][ct][k][i|(1<<k)], ld[cr][ct][j][i]+g[cr][j][cr][k]);
  30. 			}
  31. 		}
  32. 	}
  33. }
  34.  
  35. void pre_calc(int cr){
  36. 	if(f[cr] == m[cr]) return;
  37. 	if(f[cr] == 1){
  38. 		d1[cr] = m[cr]==1?0:INF;
  39. 		ng = true;
  40. 	} else if(f[cr] == 2){
  41. 		d2[cr] = ld[cr][0][1][(1<<m[cr])-1];
  42. 	} else if(f[cr] == 3){
  43. 		for(int i = 0; i < 3; i++){
  44. 			int j = (i+1)%3, k = (i+2)%3;
  45. 			d3a[cr][i] = ld[cr][j][k][((1<<m[cr])-1)^(1<<i)];
  46. 			d3b[cr][i] = ld[cr][j][k][((1<<m[cr])-1)];
  47. 		}
  48. 	} else {
  49. 		for(int i = 0; i < 4; i++){
  50. 			for(int j = i+1; j < 4; j++){
  51. 				int k = 0;
  52. 				while(k==i||k==j) k++;
  53. 				int l = k+1;
  54. 				while(l==i||l==j) l++;
  55. 				d4b[cr][i][j] = d4b[cr][j][i] = ld[cr][i][j][((1<<m[cr])-1)^(1<<k)^(1<<l)];
  56. 				d4c[cr][i][j][k] = d4c[cr][j][i][k] = ld[cr][i][j][((1<<m[cr])-1)^(1<<l)];
  57. 				d4c[cr][i][j][l] = d4c[cr][j][i][l] = ld[cr][i][j][((1<<m[cr])-1)^(1<<k)];
  58. 				d4d[cr][i][j] = d4d[cr][j][i] = ld[cr][i][j][((1<<m[cr])-1)];
  59. 				for(int b = (1<<i)|(1<<j); b < 1<<m[cr]; b+=1<<4)
  60. 					chmin(d4a[cr][i][j], ld[cr][i][j][b]+ld[cr][k][l][(1<<m[cr])-b-1]);
  61. 				/*for(int b = 0; b < 1<<m[cr]; b++){
  62. 					if(1&((i>>k)|(i>>l))) continue;
  63. 					chmin(d4a[cr][i][j], ld[cr][i][j][b]+ld[cr][k][l][(1<<m[cr])-b]);
  64. 				}*/
  65.  
  66. 			}
  67. 		}
  68. 	}
  69. }
  70.  
  71. int gtsp(){
  72. 	memset(gd, 9, sizeof(gd));
  73. 	int start = u1[0];
  74. 	if(f[0]==3) start = (start+1)%3;
  75. 	//start = 0; // debug
  76. 	gd[start][0] = 0;
  77. 	for(int i = 0; i < 1<<sf; i++){
  78. 		for(int j = 0; j < sf; j++){
  79. 			if(gd[j][i]>=INF) continue;
  80. 			int f1 = c1[j], f2 = c2[j];
  81. 			for(int k = 0; k < sf; k++){
  82. 				if((1&(i>>k))) continue;
  83. 				int t1 = c1[k], t2 = c2[k];
  84. 				int kk = k-t2;
  85. 				int sz = f[t1];
  86. 				int pt = pat[t1];
  87. 				int r = gd[j][i]+g[f1][f2][t1][t2];
  88. 				if(r>=INF) continue; 
  89. 				//if(f1==t1 && f[t1]!=m[t1]) continue; // debug
  90. 				//cerr<<"t1: "<<t1<<" t2: "<<t2<<" sz: "<<sz<<" pt: "<<pt<<endl;
  91. 				if(f[t1]==m[t1]){
  92. 					chmin(gd[k][i|(1<<k)], r);
  93. 				} else if(f[t1]==2){
  94. 					int k2 = kk+1-t2;
  95. 					chmin(gd[k2][i|(1<<k)|(1<<k2)], r);
  96. 				} else if(f[t1]==3){
  97. 					int k2 = kk+3-t2-u1[t1];
  98. 					if(pt==0){
  99. 						if(u1[t1]==t2){
  100. 							chmin(gd[k][i|(1<<k)], r);
  101. 						} else {
  102. 							chmin(gd[k2][i|(1<<k)|(1<<k2)], r);
  103. 						}
  104. 					} else {
  105. 						if(u1[t1]!=t2){
  106. 							chmin(gd[k2][i|(1<<kk)|(1<<(kk+1))|(1<<(kk+2))], r);
  107. 						}
  108. 					}
  109. 				} else {
  110. 					int tt = -1;
  111. 					if(t2==u1[t1]) tt = u2[t1];
  112. 					else if(t2==u2[t1]) tt = u1[t1];
  113. 					int k2 = kk+tt;
  114. 					if(pt==0){
  115. 						if(tt<0){
  116. 							tt = 6-t2-u1[t1]-u2[t1];
  117. 							k2 = kk+tt;
  118. 						}
  119. 						chmin(gd[k2][i|(1<<k)|(1<<k2)], r);
  120. 						//cerr<<"a: "<<u1[t1]<<" b: "<<u2[t1]<<" c: "<<t2<<" d: "<<tt<<endl;
  121. 					} else if(pt==1){
  122. 						if(tt<0){
  123. 							chmin(gd[k][i|(1<<k)], r);
  124. 						} else {
  125. 							chmin(gd[k2][i|(1<<k)|(1<<k2)], r);
  126. 						}
  127. 					} else if(pt==2){
  128. 						if(tt>=0){
  129. 							int k3 = kk+u3[t1];
  130. 							chmin(gd[k2][i|(1<<k)|(1<<k2)|(1<<k3)], r);
  131. 						} else if(t2!=u3[t1]){
  132. 							chmin(gd[k][i|(1<<k)], r);
  133. 						}
  134. 					} else {
  135. 						if(tt>=0){
  136. 							chmin(gd[k2][i|(1<<kk)|(1<<(kk+1))|(1<<(kk+2))|(1<<(kk+3))], r);
  137. 						}
  138. 					}
  139. 				}
  140. 			}
  141. 		}
  142. 	}
  143. 	int res = gd[start][(1<<sf)-1];
  144. 	//if(res>=INF) return INF;
  145. 	//cerr<<"initial: "<<res<<endl;
  146. 	for(int i = 0; i < n; i++){
  147. 		int res_old = res;
  148. 		int pt = pat[i];
  149. 		if(f[i]==m[i]) continue;
  150. 		if(f[i]==2){
  151. 			res += d2[i];
  152. 		} else if(f[i]==3){
  153. 			res += pt==0?d3a[i][u1[i]]:d3b[i][u1[i]];
  154. 		} else {
  155. 			res +=
  156. 				pt==0 ? d4a[i][u1[i]][u2[i]]        :
  157. 				pt==1 ? d4b[i][u1[i]][u2[i]]        :
  158. 				pt==2 ? d4c[i][u1[i]][u2[i]][u3[i]] :
  159. 				        d4d[i][u1[i]][u2[i]]        ;
  160. 		}
  161. 		cerr<<i<<" "<<f[i]<<": "<<" "<<pt<<" "<<u1[i]<<" "<<u2[i]<<" "<<u3[i]<<"   "<<res-res_old<<endl;
  162. 	}
  163. 	cerr<<res<<endl;
  164. 	return res;
  165. }
  166.  
  167. void init(){
  168. 	memset(g, 9, sizeof(g));
  169. 	memset(ld, 9, sizeof(ld));
  170. 	memset(d1, 9, sizeof(d1));
  171. 	memset(d2, 9, sizeof(d2));
  172. 	memset(d3a, 9, sizeof(d3a));
  173. 	memset(d3b, 9, sizeof(d3b));
  174. 	memset(d4a, 9, sizeof(d4a));
  175. 	memset(d4b, 9, sizeof(d4b));
  176. 	memset(d4c, 9, sizeof(d4c));
  177. 	memset(d4d, 9, sizeof(d4d));
  178. }
  179.  
  180. bool u4(int pos){
  181. 	if(u2[pos]<3){
  182. 		u2[pos]++;
  183. 		return true;
  184. 	}
  185. 	if(u1[pos]<2){
  186. 		u1[pos]++;
  187. 		u2[pos] = u1[pos]+1;
  188. 		return true;
  189. 	}
  190. 	u1[pos] = 0;
  191. 	u2[pos] = 1;
  192. 	pat[pos]++;
  193. 	return false;
  194. }
  195.  
  196. int main(){
  197. 	init();
  198. 	int K;
  199. 	cin>>n>>K;
  200. 	for(int i = 0; i < n; i++) cin>>m[i];
  201. 	for(int i = 0; i < n; i++){
  202. 		cin>>f[i];
  203. 		sf += f[i];
  204. 	}
  205. 	if(n==1){
  206. 		sf = m[0];
  207. 		for(int i = m[0]-1; i >= 0; i--)
  208. 			m[i] = f[i] = 1;
  209. 	}
  210. 	for(int i = 0; i < K; i++){
  211. 		int a, b, c, d, e;
  212. 		cin>>a>>b>>c>>d>>e;
  213. 		a--; b--; c--; d--;
  214. 		if(n==1) swap(a, b), swap(c, d);
  215. 		g[a][b][c][d] = g[c][d][a][b] = e;
  216. 	}
  217. 	if(n==1 && sf==1){
  218. 		cout<<0<<endl;
  219. 		return 0;
  220. 	}
  221. 	for(int i = 0, cc1 = 0, cc2 = 0; i < sf; i++){
  222. 		if(cc2>=f[cc1]){
  223. 			cc1++;
  224. 			cc2 = 0;
  225. 		}
  226. 		//cerr<<"c1: "<<cc1<<" c2: "<<cc2<<endl;
  227. 		c1[i] = cc1;
  228. 		c2[i] = cc2++;
  229. 	}
  230. 	for(int i = 0; i < n; i++){
  231. 		for(int j = 0; j < f[i]; j++)
  232. 			ltsp(i, j);
  233. 		pre_calc(i);
  234. 	}
  235. 	if(ng){
  236. 		cout<<-1<<endl;
  237. 		return 0;
  238. 	}
  239. 	for(int i = 0; i < N; i++){
  240. 		u2[i] = 1;
  241. 		u3[i] = 2;
  242. 	}
  243. 	int res = INF;
  244. 	for(;;){
  245. 		chmin(res, gtsp());
  246. 		//cerr<<"current answer: "<<res<<endl;
  247. 		//if(res<401) break;
  248. 		int pos = -1;
  249. 		while(++pos < n){
  250. 			if(f[pos]==m[pos]) continue;
  251. 			if(f[pos]==3){
  252. 				if(u1[pos]<2){
  253. 					u1[pos]++;
  254. 					break;
  255. 				}
  256. 				u1[pos] = 0;
  257. 				if(pat[pos]<1){
  258. 					pat[pos]++;
  259. 					break;
  260. 				}
  261. 				pat[pos] = 0;
  262. 			} else if(f[pos]==4){
  263. 				if(pat[pos]<2){
  264. 					u4(pos);
  265. 					break;
  266. 				}
  267. 				if(pat[pos]==2){
  268. 					int t1 = u3[pos], t2 = 6-u1[pos]-u2[pos]-t1;
  269. 					if(t1 < t2){
  270. 						u3[pos] = t2;
  271. 						break;
  272. 					}
  273. 					if(u2[pos]<3){
  274. 						t1 = u2[pos];
  275. 						u2[pos]++;
  276. 						u3[pos] = min(u2[pos]-1, 7-u1[pos]-2*u2[pos]);
  277. 						break;
  278. 					}
  279. 					if(u1[pos]<2){
  280. 						u1[pos]++;
  281. 						u2[pos] = u1[pos]+1;
  282. 						u3[pos] = min(u1[pos]-1, 7-2*u1[pos]-u2[pos]);
  283. 						break;
  284. 					}
  285. 					u1[pos] = 0;
  286. 					u2[pos] = 1;
  287. 					u3[pos] = 2;
  288. 					pat[pos]++;
  289. 					break;
  290. 				}
  291. 				if(u4(pos)) break;
  292. 				pat[pos] = 0;
  293. 			}
  294. 		}
  295. 		if(pos == n) break;
  296. 	}
  297. 	cout<<(res==INF?-1:res)<<endl;
  298. 	return 0;
  299. }
  300.  
Success #stdin #stdout #stderr 0.15s 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
stderr 
4
https://ideone.com/s13jcw
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!