虫洞 起点 终点给你N条虫洞虫洞所替代距离虫洞起点 终点

    xiaoxiao2021-03-26  10

    

    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

    转载请注明原文地址: https://ju.6miu.com/read-600289.html

    最新回复(0)