Problem: Example

Input

3 3 1
1 1 10 10
AAA
A..
A..


Output

100

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define INF 1LL<<60
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,P> PP;

struct data{
	ll cost;
	int c,v,bit;
	data(){}
	data(int cc,int vv,int bb,ll ccost){
		c=cc;
		v=vv;
		bit=bb;
		cost=ccost;
	}
	bool operator<(const data &d)const{
		return cost>d.cost;
	}
};

int h,w,K;
int sx,sy;
ll tmo,tc;
int fie[51][51];
vector<P> rooms[26];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ll cost[12][12][12];
ll path[12][12][12][12];
ll cost2[12][12][12][12];
ll dp[12][12][1<<12];
ll dp2[13][1<<12];
P roomid[51][51];

void read_input(){
	scanf("%d%d%d",&h,&w,&K);
	scanf("%d%d%lld%lld",&sy,&sx,&tmo,&tc);
	sy--;
	sx--;
	memset(fie,-1,sizeof(fie));
	for(int i=0;i<h;i++){
		string str;
		cin >> str;
		for(int j=0;j<w;j++){
			if(str[j]>='A' && str[j]<='Z'){
				fie[i][j]=(str[j]-'A');
			}
		}
	}
}

void calc_checkunit(int c){
	if(rooms[c].size()==0)return;
	ll** dist=new ll*[h];
	for(int i=0;i<h;i++){
		dist[i]=new ll[w];
	}
	ll** dist2=new ll*[12];
	for(int i=0;i<12;i++){
		dist2[i]=new ll[12];
		for(int j=0;j<12;j++){
			dist2[i][j]=INF;
		}
	}
	int rs=rooms[c].size();
	for(int i=0;i<rs;i++){
		queue<P> que;
		for(int j=0;j<h;j++){
			for(int k=0;k<w;k++){
				dist[j][k]=-1;
			}
		}
		que.push(P(rooms[c][i].first,rooms[c][i].second));
		dist[rooms[c][i].first][rooms[c][i].second]=0;
		while(que.size()){
			P p=que.front();
			que.pop();
			if(roomid[p.first][p.second].first==c){
				dist2[i][roomid[p.first][p.second].second]=dist[p.first][p.second];
			}
			if(roomid[p.first][p.second].first>=0){
				path[c][i][roomid[p.first][p.second].first][roomid[p.first][p.second].second]=dist[p.first][p.second];
			}
			for(int j=0;j<4;j++){
				int nx=dx[j]+p.second;
				int ny=dy[j]+p.first;
				if(nx>=0 && nx<w && ny>=0 && ny<h){
					if(fie[ny][nx]>=0 && dist[ny][nx]==-1){
						dist[ny][nx]=dist[p.first][p.second]+tmo;
						que.push(P(ny,nx));
					}
				}
			}
		}
	}
	ll** dist3=new ll*[rs];
	for(int i=0;i<rs;i++){
		dist3[i]=new ll[1<<rs];
	}
	for(int i=0;i<rs;i++){
		for(int j=0;j<rs;j++){
			for(int k=0;k<(1<<rs);k++){
				dist3[j][k]=INF;
			}
		}
		dist3[i][1<<i]=tc;
		priority_queue<PP,vector<PP>,greater<PP> > que;
		que.push(PP(tc,P(i,1<<i)));
		while(que.size()){
			PP p=que.top();
			que.pop();
			ll cc=p.first;
			int cv=p.second.first;
			int cb=p.second.second;
			if(dist3[cv][cb]<cc)continue;
			//printf("c=%d %d %d %lld\n",c,cv,cb,cc);
			for(int j=0;j<rs;j++){
				if(!(cb>>j & 1)){
					if(dist3[j][cb+(1<<j)]>cc+dist2[cv][j]+tc){
						dist3[j][cb+(1<<j)]=cc+dist2[cv][j]+tc;
						que.push(PP(dist3[j][cb+(1<<j)],P(j,cb+(1<<j))));
					}
				}
			}
		}
		for(int j=0;j<rs;j++){
			cost[c][i][j]=dist3[j][(1<<rs)-1];
			//printf("%d %d %d %lld\n",c,i,j,cost[c][i][j]);
		}
	}
	delete[] dist;
	delete[] dist2;
}

int main(void){
	read_input();
	for(int i=0;i<12;i++){
		for(int j=0;j<12;j++){
			for(int k=0;k<12;k++){
				for(int l=0;l<12;l++){
					path[i][j][k][l]=INF;
				}
			}
		}
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<h;j++){
			roomid[i][j]=P(-1,-1);
		}
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(fie[i][j]>=0){
				int cnt=0;
				for(int k=0;k<4;k++){
					int nx=j+dx[k];
					int ny=i+dy[k];
					if(nx>=0 && nx<w && ny>=0 && ny<h){
						if(fie[ny][nx]>=0)cnt++;
					}
				}
				if(cnt<=1){
					roomid[i][j]=P(fie[i][j],rooms[fie[i][j]].size());
					rooms[fie[i][j]].push_back(P(i,j));
				}
			}
		}
	}
	//printf("done\n");
	for(int i=0;i<26;i++){
		calc_checkunit(i);
	}

	ll **dist=new ll*[h];
	for(int i=0;i<h;i++){
		dist[i]=new ll[w];
	}
	queue<P> que;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			dist[i][j]=-1;
		}
	}
	que.push(P(sy,sx));
	dist[sy][sx]=0;
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int j=0;j<4;j++){
			int nx=dx[j]+p.second;
			int ny=dy[j]+p.first;
			if(nx>=0 && nx<w && ny>=0 && ny<h){
				if(fie[ny][nx]>=0 && dist[ny][nx]==-1){
					dist[ny][nx]=dist[p.first][p.second]+tmo;
					que.push(P(ny,nx));
				}
			}
		}
	}
	//printf("done\n");
	for(int i=0;i<12;i++){
		for(int j=0;j<12;j++){
			for(int k=0;k<(1<<12);k++){
				dp[i][j][k]=INF;
			}
			for(int k=0;k<12;k++){
				for(int l=0;l<12;l++){
					cost2[i][j][k][l]=INF;
				}
			}
		}
	}
	for(int i=0;i<12;i++){
		for(int j=0;j<rooms[i].size();j++){
			for(int k=0;k<12;k++){
				if(i==k)continue;
				for(int l=0;l<rooms[k].size();l++){
					for(int a=0;a<rooms[k].size();a++){
						cost2[i][j][k][l]=min(cost2[i][j][k][l],cost[k][a][l]+path[i][j][k][a]);
					}
				}
			}
		}
	}
	priority_queue<data> que2;
	for(int i=0;i<12;i++){
		for(int j=0;j<rooms[i].size();j++){
			for(int k=0;k<rooms[i].size();k++){
				ll nc=dist[rooms[i][j].first][rooms[i][j].second]+cost[i][j][k];
				if(nc<dp[i][k][1<<i]){
					dp[i][k][1<<i]=nc;
					//printf("%d %d %d %lld\n",i,k,1<<i,nc);
					que2.push(data(i,k,1<<i,nc));
				}
			}
		}
	}
	while(que2.size()){
		data d=que2.top();
		que2.pop();
		if(d.cost>dp[d.c][d.v][d.bit])continue;
		//if(__builtin_popcount(d.bit)==1)printf("que2 %d %d %d %lld\n",d.c,d.v,d.bit,d.cost);
		for(int i=0;i<12;i++){
			if(rooms[i].size()==0 || (d.bit>>i & 1))continue;
			for(int j=0;j<rooms[i].size();j++){
				//printf("cost2 %d %d %lld\n",i,j,cost2[d.c][d.v][i][j]);
				if(dp[i][j][d.bit+(1<<i)]>d.cost+cost2[d.c][d.v][i][j]){
					dp[i][j][d.bit+(1<<i)]=d.cost+cost2[d.c][d.v][i][j];
					que2.push(data(i,j,d.bit+(1<<i),dp[i][j][d.bit+(1<<i)]));
				}
			}
		}
	}
	int ansbit=0;
	for(int i=0;i<12;i++){
		if(rooms[i].size()>0)ansbit+=(1<<i);
	}
	for(int i=0;i<=ansbit;i++){
		dp2[1][i]=INF;
		for(int j=0;j<12;j++){
			for(int k=0;k<rooms[j].size();k++){
				dp2[1][i]=min(dp2[1][i],dp[j][k][i]+dist[rooms[j][k].first][rooms[j][k].second]);
			}
		}
		//if(__builtin_popcount(i)==1)printf("1 %d %lld\n",i,dp2[1][i]);
	}
	
	ll ans=dp2[1][ansbit];
	for(int i=1;i<K;i++){
		for(int j=1;j<=ansbit;j++){
			dp2[i+1][j]=INF;
			int pb=j-1;
			pb=pb&j;
			while(pb!=j){
				for(int k=1;k<=i;k++){
					dp2[i+1][j]=min(max(dp2[k][pb],dp2[i+1-k][j-pb]),dp2[i+1][j]);
				}
				pb=pb-1;
				pb=pb&j;
			}
			//printf("%d %d %lld\n",i+1,j,dp2[i+1][j]);
		}
		ans=min(dp2[i+1][ansbit],ans);
	}
	printf("%lld\n",ans);
	return 0;
}