package xj;
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class ChongDong { static int T, N, sx, sy, ex, ey; static int data[][]; static int mind; 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(); sx=sc.nextInt(); sy=sc.nextInt(); ex=sc.nextInt(); ey=sc.nextInt(); data=new int [N][5]; used=new boolean [N]; 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 = 0; i < N; i++) { dfs(0,i,0,sx,sy); } /*for (int i = 0; i < N; i++) { for (int j = 0; j < 5; j++) { System.out.print(" "+data[i][j]); }System.out.println(); }*/ System.out.println(mind); } }
private static void dfs(int step, int num, int dis, int sx, int sy) { if(step>num){ if(dis+dis(sx,sy,ex,ey)<mind){mind=dis+dis(sx,sy,ex,ey);}//需要加入最后长度 return; } for (int i = 0; i < N; i++) { if(!used[i]){ used[i]=true; //zuo 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]); //you 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]); //huishou 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 8 10 62 62
