package work;
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class AChongDong { static int T, N, mind; static int sx, sy, ex, ey; static int[][] data; static boolean []used;
public static void main(String[] args) throws FileNotFoundException { /* Scanner sc=new Scanner(System.in); */ Scanner sc = new Scanner(new File("src/chongdong")); T=sc.nextInt(); for (int t = 0; t < T; t++) { N=sc.nextInt(); data=new int [N][5]; used=new boolean[N]; sx=sc.nextInt(); sy=sc.nextInt(); ex=sc.nextInt(); ey=sc.nextInt(); for (int i = 0; i < N; i++) { for (int j = 0; j < 5; j++) { data[i][j]=sc.nextInt(); } } mind=dis(sx,sy,ex,ey); for (int i = 1; i <= N; i++) { dfs(0,i,0,sx,sy); } System.out.println(mind); } }
private static void dfs(int step, int num, int dis, int sx, int sy) { if(dis+dis(sx,sy,ex,ey)>mind){return;} if(step==num){ mind=dis+dis(sx,sy,ex,ey); return; } for (int i = 0; i < N; i++) { if(!used[i]){ used[i]=true; // dis+=(dis(sx,sy,data[i][0],data[i][1])+data[i][4]); dfs(step+1,num,dis,data[i][2],data[i][3]); dis-=(dis(sx,sy,data[i][0],data[i][1])+data[i][4]); // dis+=(dis(sx,sy,data[i][2],data[i][3])+data[i][4]); dfs(step+1,num,dis,data[i][0],data[i][1]); dis-=(dis(sx,sy,data[i][2],data[i][3])+data[i][4]); used[i]=false; } } } private static int dis(int sx, int sy, int ex, int ey) { int dx = (sx - ex > 0) ? (sx - ex) : (ex - sx); int dy = (sy - ey > 0) ? (sy - ey) : (ey - sy); return dx + dy; }
}
、、input
11 4 5 5 100 100 20 2 1000 2 1 -100 20 30 9000 1 4 4 -99 -99 2 -4 5 29 100 1 3 1 1 9 9 -1 2 9 7 1 0 0 9 0 1 -3 -3 8 8 2 4 900 900 1000 1000 800 800 1001 1001 1 1001 1001 900 900 1 901 901 999 999 1 902 900 1000 999 1 3 1 1 1 200 2 5 2 100 10 3 1 3 50 2 7 8 7 90 20 2 0 0 0 200 1 2 1 150 20 1 5 1 90 21 1 1 1 1 10 1 1 1 7 2 1 1 1 10 1 1 1 7 1 2 2 1 1 10 10 1 1 5 5 3 6 6 9 9 1 2 5 5 10 10 1 1 3 3 1 5 5 18 18 1 2 0 0 0 200 -30 2 -5 2 5 -31 3 -31 190 7 2 0 0 0 200 -31 3 -31 190 7 -30 2 -5 2 5
、、output
81 6 3 116 74 5 5 13 10 82 82
