Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.5 kB
2
Indexable
#include <iostream>

using namespace std;

int N, Sx, Sy, Hx, Hy, T;
int posX[20], posY[20];
int map[20][20];
bool visited[20];
int ans, minA;

int cal(int a, int b){
	if(a > b)
		return a - b;
	return b - a;
}
void distance(){
	for(int i = 0; i < N + 1; i++){
		for(int j = i + 1; j <= N + 1; j++){
			map[i][j] = cal(posX[i], posX[j]) + cal(posY[i], posY[j]);
			map[j][i] = cal(posX[i], posX[j]) + cal(posY[i], posY[j]);
		}
	}
}
void backtrack(int k, int count){
	if(ans >= minA){
		return;
	}
	if(count == N + 1){
		ans += map[k][N + 1];
		if(ans < minA){
			minA = ans;
		}
		ans -= map[k][N + 1];
		return;
	}
	for(int i = 1; i <= N; i++){
		if(visited[i] == false && map[k][i] != 0){
			visited[i] = true;
			ans += map[k][i];
			backtrack(i, count + 1);
			ans -= map[k][i];
			visited[i] = false;
		}
	}
}
int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> Sx >> Sy >> Hx >> Hy;
		cin >> N;
		posX[0] = Sx;
		posY[0] = Sy;

		for(int i = 1; i <= N; i++){
			cin >> posX[i] >> posY[i];
		}
		posX[N + 1] = Hx;
		posY[N + 1] = Hy;

		for(int i = 0; i <= N + 1; i++){
			visited[i] = false;
		}
		for(int i = 0; i <= N + 1; i++){
			for(int j = 0; j <= N + 1; j++){
				map[i][j] = 0;
			}
		}
		distance();
		ans = 0; 
		minA = 10000000;
		backtrack(0, 1);
		cout <<"Case #" << tc <<" " << minA << endl;
	}
	return 0;
}
Leave a Comment