MLE20分蒟蒻求助

#include <bits/stdc++.h>

using namespace std;

int n, m, K;
int mat[501][501], st[501][501], vis[501][501], dis[21][21], dp[70001][21];
int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

string s[70001][21];

queue<pair<int, pair<int, int> > > q;

pair<int, int> p[28];

void init_vars(){
	// type your initiating code...
}

void bfs(int ord){
    while(q.size()) q.pop();
	q.push(make_pair(0, make_pair(p[ord].first, p[ord].second)));
	while(!q.empty()){
		//cout << q.size() << endl;
		pair<int, pair<int, int> > x = q.front(); q.pop();
		vis[x.second.first][x.second.second] = 1;
		if(st[x.second.first][x.second.second])
			dis[st[x.second.first][x.second.second]][ord] = x.first;
		for(int i = 0; i < 4; i++){
			int xx = x.second.first + d[i][0],
				yy = x.second.second + d[i][1];
			if(!mat[xx][yy] || vis[xx][yy]) continue;
			q.push(make_pair(x.first + 1, make_pair(xx, yy)));
		}
	}
}

void solve(int testcase, ...){
	init_vars();
	cin >> n >> m >> K;
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	for(int i = 1; i <= n; i++){
		string s; cin >> s;
		for(int j = 1; j <= m; j++){
			if(s[j - 1] == '.') mat[i][j] = 1;
			else if(s[j - 1] == '*') mat[i][j] = 0;
			else mat[i][j] = 1,
				 p[s[j - 1] - 'A' + 1] = make_pair(i, j),
				 st[i][j] = s[j - 1] - 'A' + 1;
		}
	}
	vector<int> vec;
	for(int i = 1; i <= 26; i++){
		if(p[i].first + p[i].second == 0) continue;
		memset(vis, 0, sizeof(vis)); bfs(i);
		vec.push_back(i);
	}
	//cout << "Scheißen" << endl;
	int ans = 0x3f3f3f3f; string san;
	dp[1][0] = 0, s[1][0] = "A";
	for(int i = 0; i < (1 << K); i++)
		for(int j = 0; j < K; j++) for(int k = 0; k < K; k++){
			if(((i >> j) & 1) && ((i >> k) & 1) && k != j){
				int sum = dp[i ^ (1 << j)][k] + dis[vec[j]][vec[k]];
				string t = s[i ^ (1 << j)][k] + "A"; t[t.length() - 1] += vec[j] - 1;
				if(dp[i][j] >= sum){
					if(dp[i][j] > sum || s[i][j] > t)
						s[i][j] = t;
					dp[i][j] = sum;
				}
			}
	}
	for(int i = 0; i < K; i++){
		if(ans >= dp[(1 << K) - 1][i]){
			if(ans > dp[(1 << K) - 1][i] || san > s[(1 << K) - 1][i]){
				san = s[(1 << K) - 1][i]; 
			}
			ans = dp[(1 << K) - 1][i];
		}
	}
	cout << ans << endl << san << endl;
}

signed main(){
#ifdef files
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	solve(1);
#ifdef files
	fclose(stdin); fclose(stdout);
#endif
	return 0;
}