Untitled

public class abc {
	static int n;
	static int a, b, c;
	static double matrix[][], key[];
	static boolean visited[][], visit[];

    public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("C:/SCS/ADV2/src/test/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt();
			a = sc.nextInt();
			b = sc.nextInt();
			c = sc.nextInt();
			visited = new boolean[n + 1][n + 1];
			matrix = new double[n + 1][n + 1];
			visit = new boolean[n + 1];
			key = new double[n + 1];
			
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					matrix[i][j] = sc.nextDouble();
					if (i != j && !visited[i][j]) {
						visited[i][j] = true;
						matrix[i][j] = solve(matrix[i][j]);
					}
				}
			}

			for (int i = 1; i <= n; i++) {
				key[i] = Double.MAX_VALUE;
			}
		
			prim();
			double ans = 0.0;
			for (int i = 1; i <= n; i++) {
				ans += key[i];
			}

			System.out.printf("#%d %.3f\n", tc, ans);
		}
		sc.close();
	}

	static double solve(double value) {
		double left = 0.0, right = value;
		while (right - left > 1e-6) {
			double mid = left + (right - left) / 2.0;
			double num = a * Math.pow(mid, 3) + b * Math.pow(mid, 2) + c;
			if (value == num) {
				return mid;
			} else if (value < num) {
				right = mid;
			} else {
				left = mid;
			}
		}
		return left;
	}

	static int findMin() {
		double min = Double.MAX_VALUE;
		int min_idx = 0;
		for (int i = 1; i <= n; i++) {
			if (!visit[i] && key[i] < min) {
				min = key[i];
				min_idx = i;
			}
		}
		return min_idx;
	}

	static void prim() {
		key[1] = 0;
		for (int i = 1; i <= n - 1; i++) {
			int u = findMin();

			visit[u] = true;
			for (int v = 1; v <= n; v++) {
				if (!visit[v] && u != v && key[v] > matrix[u][v]) {
					key[v] = matrix[u][v];
				}
			}
		}
	}
}

#1 6.000
#2 9.119
#3 8.060
#4 26.371
#5 18.983
#6 29.117
#7 18.328
#8 30.336
#9 22.253
#10 33.033
#11 11123563.825
#12 30373854.103
#13 7567499.915
#14 11797034.099
#15 8463058.600
#16 2439733.779
#17 16178946.582
#18 9403868.822
#19 6891839.275
#20 7824343.076
#21 8766828.461
#22 7565958.813
#23 6602238.269
#24 11277332.021
#25 4449955.050
#26 7952083.534
#27 3242380.583
#28 4534051.931
#29 2589291.416
#30 3826996.791
#31 3513981.974
#32 6257813.395
#33 7217559.068
#34 8888707.143
#35 5783796.235
#36 10532357.478
#37 5135140.983
#38 10406849.351
#39 4593651.588
#40 5006037.684
#41 15247286.743
#42 11474689.224
#43 8663165.338
#44 10914022.383
#45 7609414.126
#46 12268572.649
#47 14053342.152
#48 13705856.786
#49 10789210.075
#50 18318118.359