我这还能优化的吗?
查看原帖
我这还能优化的吗?
162644
Clannad111楼主2020/5/8 16:19
import java.util.*;
import java.math.*;
import java.io.*;

public class Main{
	
	public static double min=999999999;
	public static int[] record = new int[16];
	public static void dfs(double[][] book, int step, int n, int num, double total) {		
		if(total>=min) {
			return;
		}	
		if(num<=0) {
			if(total<min)
				min = total;
			return;
		}
		for(int i=1; i<=n; i++) {
			if(record[i]==0) {
				total+=book[step][i];
				record[i]=1;
				dfs(book, i, n, num-1, total);
				total-=book[step][i];
				record[i]=0;
			}
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		double[][] book = new double[n+1][n+1];
		double[][] station = new double[n+1][2];
		int x,y;
		for(int i=1; i<=n; i++) {
			station[i][0] = in.nextDouble();
			station[i][1] = in.nextDouble();
		}
		for(int i=1; i<=n; i++) {
			book[0][i] = Math.sqrt(station[i][0]*station[i][0]+station[i][1]*station[i][1]);
			book[i][0] = book[0][i];
			for(int j=i+1; j<=n; j++) {
				book[i][j] = Math.sqrt((station[i][0]-station[j][0])*(station[i][0]-station[j][0])+(station[i][1]-station[j][1])*(station[i][1]-station[j][1]));
				book[j][i] = book[i][j];
			}
		}
		for(int i=1; i<=n; i++) {
			record[i]=1;
			dfs(book, i, n, n-1, book[0][i]);
			record[i]=0;
		}
		System.out.printf("%.2f",min);
 	}
}
2020/5/8 16:19
加载中...