Untitled

 avatar
unknown
plain_text
9 months ago
1.2 kB
1
Indexable
#include <iostream>
using namespace std;
#pragma warning (disable:4996)
int sx,sy,hx,hy,n,min1;
int visit[20];
int weight[20][20];
struct Point{
	int x;
	int y;
};
Point a[20];
void backtrack(int vitri, int dem, int kq){
	if (dem==n){
		if (kq+weight[vitri][n+1]<min1){
			min1=kq+weight[vitri][n+1];
		}
		return;
	}
	if (kq+weight[vitri][n+1]>min1){
		return;
	}
	for (int i=1; i<=n; i++){
		if (visit[i]==0){
			visit[i]=1;
			backtrack(i,dem+1,kq+weight[vitri][i]);
			visit[i]=0;
		}
	}
};

int main(){
	freopen("Text.txt","r",stdin);
	int tc;
	cin >>tc;
	for (int t=1; t<=tc; t++){
		cin >> sx >> sy >> hx >> hy;
		cin >> n;
		a[0].x=sx;
		a[0].y=sy;
		a[n+1].x=hx;
		a[n+1].y=hy;
		visit[0]=0;
		visit[n+1]=0;
		for (int i=1; i<=n; i++){
			cin >> a[i].x >> a[i].y;
			visit[i]=0;
		}
		for (int i=0; i<n+1; i++){
			for (int j=i+1; j<=n+1; j++){
				int u,v;
				if (a[i].x-a[j].x >=0){
					u=a[i].x-a[j].x;
				}
				else{
					u=a[j].x-a[i].x;
				}
				if (a[i].y-a[j].y >=0){
					v=a[i].y-a[j].y;
				}
				else{
					v=a[j].y-a[i].y;
				}
				weight[i][j]=u+v;
				weight[j][i]=u+v;
			}
		}
		min1=10000000;
		backtrack(0,0,0);
		cout<<"Case #"<<t<<" "<<min1<<endl;
	}
	return 0;
}
Editor is loading...
Leave a Comment