Hugo Giao Hang

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
package Hugo_Giao_Hang;

import java.io.FileInputStream;
import java.util.Scanner;

public class hugo_giao_hang {
	static int hx, hy, sx, sy, n, Ans;
	static int [][] arr, map;
	static int [] visit;
	
	static int distance(int i, int j) {
		int a = arr[i][0] - arr[j][0];
		int b = arr[i][1] - arr[j][1];
		if (a < 0) a = 0 - a;
		if (b < 0) b = 0 - b;
		return a+b;
	}
	
	
	static void createMatrix() {
		for (int i = 0; i < n + 2; i++) {
			for (int j = 0; j < n + 2; j++) {
				int x = distance(i, j);
				map[i][j] = x;
			}
		}
	}
	
	static void Try(int x, int sum_distance, int count) {
		if (count == n) {
			sum_distance += map[x][n+1];
			if (sum_distance < Ans) Ans = sum_distance;
			return;
		}
		if (Ans < sum_distance) return;
		for (int i = 1; i <= n; i++) {
			if (visit[i] == 0) {
				visit[i] = 1;
				Try(i, sum_distance + map[x][i], count+1);
				visit[i] = 0;
			}
		}
	}
	
	
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("D://Trainee//SRV_training//src//Hugo_Giao_Hang//giao_hang.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			sx = sc.nextInt();
			sy = sc.nextInt();
			hx = sc.nextInt();
			hy = sc.nextInt();
			n = sc.nextInt();
			arr = new int [n+2][2];
			for(int i = 1; i < n+1; i++) {
				arr[i][0] = sc.nextInt();
				arr[i][1] = sc.nextInt();
			}
			arr[0][0] = sx;
			arr[0][1] = sy;
			arr[n+1][0] = hx;
			arr[n+1][1] = hy;
			map = new int [n+2][n+2];
			createMatrix();
			Ans = 1000000000;
			visit = new int [n+2];
			visit[0] = 1;
			Try(0, 0, 0);
			
			
			System.out.println("Case #" + test_case + " " + Ans);
		}
	}
}