Untitled
#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