AOJ 2349: World Trip

解法

できるだけ状態をまとめるようにして、場合分けする。
n=1のコーナーケースはm=1のケースに帰着できる。
正しいコード(下のと同じ)http://ideone.com/gFCDZv
場合分けしすぎてTLEするコードhttp://ideone.com/s13jcw

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define chmin(X,Y) X=min(X,Y)
#define N 15
#define F 4
int m[N], f[N];
int g[N][N][N][N];
int ld[N][F][N][1<<N], gd[N][1<<N];
int c1[N], c2[N], sf, n, fr, fp[N];
int d4[N][F][F];
bool ng;

int INF = 151587081;

void ltsp(int cr, int ct){
	ld[cr][ct][ct][1<<ct] = 0;
	int mm = m[cr];
	for(int i = 0; i < 1<<mm; i++){
		if(!(1&(i>>ct))) continue;
		for(int j = 0; j < mm; j++){
			if(ld[cr][ct][j][i]>=INF) continue;
			for(int k = 0; k < mm; k++){
				if(1&(i>>k)) continue;
				chmin(ld[cr][ct][k][i|(1<<k)], ld[cr][ct][j][i]+g[cr][j][cr][k]);
			}
		}
	}
}

void pre_calc(int cr){
	if(f[cr] == m[cr]) return;
	if(f[cr] == 1){
		ng = true;
	} else if(f[cr] == 4) {
		for(int i = 0; i < 4; i++){
			for(int j = i+1; j < 4; j++){
				int k = 0;
				while(k==i||k==j) k++;
				int l = k+1;
				while(l==i||l==j) l++;
				for(int b = (1<<i)|(1<<j); b < 1<<m[cr]; b+=1<<4)
					chmin(d4[cr][i][j], ld[cr][i][j][b]+ld[cr][k][l][(1<<m[cr])-b-1]);
			}
		}
	}
}

int gtsp(int st, int start){
	memset(gd, 9, sizeof(gd));
	gd[start][0] = 0;
	for(int i = 0; i < 1<<sf; i++){
		for(int j = 0; j < sf; j++){
			if(gd[j][i]>=INF) continue;
			int f1 = c1[j], f2 = c2[j];
			for(int k = 0; k < sf; k++){
				if((1&(i>>k))) continue;
				int t1 = c1[k], t2 = c2[k];
				int kk = k-t2;
				int sz = f[t1];
				int r = gd[j][i]+g[f1][f2][t1][t2];
				if(r>=INF) continue; 
				if(f[t1]==m[t1]){
					chmin(gd[k][i|(1<<k)], r);
				} else if(f[t1]==2){
					int k2 = kk+1-t2;
					chmin(gd[k2][i|(1<<k)|(1<<k2)], r+ld[t1][0][1][(1<<m[t1])-1]);
				} else if(f[t1]==3){
					if(7&(i>>kk)){
						if(7&((i|(1<<k))>>kk)==7){
							chmin(gd[k][i|(1<<k)], r);
						} else {
							for(int k2 = kk; k2 < kk+3; k2++){
								if(k!=k2 && !(1&(i>>k2))){
									chmin(gd[k2][i|(1<<k)|(1<<k2)], r);
								}
							}
						}
					} else {
						for(int tt = 0; tt < 3; tt++){
							int k2 = kk+tt;
							if(k==k2) continue;
							int tt2 = 3-t2-tt;
							int k3 = kk+tt2;
							chmin(gd[k2][i|(1<<k)|(1<<k2)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt2)]);
							chmin(gd[k2][i|(1<<k)|(1<<k2)|(1<<k3)], r+ld[t1][t2][tt][(1<<m[t1])-1]);
							chmin(gd[k][i|(1<<k)], r+ld[t1][tt][tt2][((1<<m[t1])-1)^(1<<t2)]);
						}
					}
				} else {
					if(1&(st>>fp[t1])){
						if(15&(i>>kk)){
							for(int k2 = kk; k2 < kk+4; k2++){
								if(k2==k || (1&(i>>k2))) continue;
								chmin(gd[k2][i|(1<<k)|(1<<k2)], r);
							}
						} else {
							for(int tt = 0; tt < 4; tt++){
								if(tt==t2) continue;
								int k2 = kk+tt;
								for(int tt2 = 0; tt2 < 4; tt2++){
									if(tt2==t2 || tt2==tt) continue;
									int tt3 = 6-t2-tt-tt2;
									int k3 = kk+tt2, k4 = kk+tt3;
									chmin(gd[k2][i|(1<<k)|(1<<k2)], r+d4[t1][t2][tt]);
								}
							}
						}
					} else {
						if(__builtin_popcount(15&(i>>kk))==1){
							for(int tt = 0; tt < 4; tt++){
								int k2 = kk+tt;
								if(!(1&(i>>k2))) continue;
								for(int tt2 = 0; tt2 < 4; tt2++){
									if(tt2==t2 || tt2==tt) continue;
									int tt3 = 6-t2-tt-tt2;
									int k3 = kk+tt2, k4 = kk+tt3;
									chmin(gd[k2][i|(1<<k)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<t2)^(1<<tt)]);
									chmin(gd[k2][i|(1<<k)|(1<<k3)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt)^(1<<tt3)]);
									chmin(gd[k2][i|(1<<k)|(1<<k3)|(1<<k4)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt)]);
								}
							}
						} else if(15&(i>>kk)){
							chmin(gd[k][i|(1<<k)], r);
						} else {
							chmin(gd[k][i|(1<<k)], r);
							for(int tt = 0; tt < 4; tt++){
								if(tt==t2) continue;
								int k2 = kk+tt;
								for(int tt2 = 0; tt2 < 4; tt2++){
									if(tt2==t2 || tt2==tt) continue;
									int tt3 = 6-t2-tt-tt2;
									int k3 = kk+tt2, k4 = kk+tt3;
									chmin(gd[k2][i|(1<<k)|(1<<k2)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt2)^(1<<tt3)]);
									chmin(gd[k2][i|(1<<k)|(1<<k2)|(1<<k3)], r+ld[t1][t2][tt][((1<<m[t1])-1)^(1<<tt3)]);
									chmin(gd[k2][i|(1<<k)|(1<<k2)|(1<<k3)|(1<<k4)], r+ld[t1][t2][tt][((1<<m[t1])-1)]);
								}
							}
						}
					}
				}
			}
		}
	}
	return gd[start][(1<<sf)-1];
}

int main(){
	memset(g, 9, sizeof(g));
	memset(ld, 9, sizeof(ld));
	memset(d4, 9, sizeof(d4));
	int K;
	cin>>n>>K;
	for(int i = 0; i < n; i++) cin>>m[i];
	for(int i = 0; i < n; i++){
		cin>>f[i];
		sf += f[i];
		if(f[i]==4){
			fp[i] = fr++;
		}
	}
	if(n==1){
		sf = m[0];
		for(int i = m[0]-1; i >= 0; i--)
			m[i] = f[i] = 1;
	}
	for(int i = 0; i < K; i++){
		int a, b, c, d, e;
		cin>>a>>b>>c>>d>>e;
		a--; b--; c--; d--;
		if(n==1) swap(a, b), swap(c, d);
		g[a][b][c][d] = g[c][d][a][b] = e;
	}
	if(n==1 && sf==1){
		cout<<0<<endl;
		return 0;
	}
	for(int i = 0, cc1 = 0, cc2 = 0; i < sf; i++){
		if(cc2>=f[cc1]){
			cc1++;
			cc2 = 0;
		}
		c1[i] = cc1;
		c2[i] = cc2++;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < f[i]; j++)
			ltsp(i, j);
		pre_calc(i);
	}
	if(ng){
		cout<<-1<<endl;
		return 0;
	}
	int res = INF;
	for(int i = 0; i < 1<<fr; i++)
		for(int j = 0; j < sf; j++)
			res = min(res, gtsp(i, j));
	cout<<(res==INF?-1:res)<<endl;
	return 0;
}