Untitled

//nang luong vu tru
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>

using namespace std;

const int MAXN = 50;
long long dist[MAXN][MAXN]; // Ma trận kề
int N, A, B, C;

// Hàm tính toán giá trị hao phí H bằng phương pháp tìm kiếm nhị phân
double findH(long long K, int A, int B, int C) {
    double low = 0.0, high = 1e6, mid;
    while (high - low > 1e-7) {
        mid = (low + high) / 2.0;
        double val = A * mid * mid * mid + B * mid * mid + C;
        if (val < K)
            low = mid;
        else
            high = mid;
    }
    return low;
}

int main() {
    int T;
    cin >> T;
    
    for (int t = 1; t <= T; t++) {
        cin >> N;
        cin >> A >> B >> C;

        // Nhập ma trận kề
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> dist[i][j];
            }
        }

        // Áp dụng Floyd-Warshall để tính đường đi ngắn nhất
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        double totalH = 0.0;

        // Tính toán hao phí nhỏ nhất
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (dist[i][j] > 0) {
                    totalH += findH(dist[i][j], A, B, C);
                }
            }
        }

        // In kết quả
        cout << "#" << t << " " << fixed << setprecision(3) << totalH << endl;
    }

    return 0;
}