Robinzon

#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;

#define LIM 100
const int INF = 1000000000;

double gip(int a, int b)
{
    return sqrt(a*a + b*b);
}
double func(int rect1[4], int rect2[4])
{
    if((rect1[0] >= rect2[0] && rect1[0] <= rect2[2]) || (rect1[2] >= rect2[0] && rect1[2] <= rect2[2]))
    {
        int y1 = abs(rect2[1] - rect1[3]);
        int y2 = abs(rect2[3] - rect1[1]);
        if(y1 < y2) return y1;
        return y2;
    }
    if((rect1[1] >= rect2[1] && rect1[1] <= rect2[3]) || (rect1[3] >= rect2[1] && rect1[3] <= rect2[3]))
    {
        int x1 = abs(rect2[0] - rect1[2]);
        int x2 = abs(rect2[2] - rect1[0]);
        if(x1 < x2) return x1;
        return x2;
    }

    if(rect1[2] < rect2[0] && rect1[3] < rect2[1])
    {
        int a = rect2[0] - rect1[2];
        int b = rect2[1] - rect1[3];
        return gip(a, b);
    }
    if(rect1[2] > rect2[0] && rect1[3] < rect2[1])
    {
        int a = rect1[0] - rect2[2];
        int b = rect2[1] - rect1[3];
        return gip(a, b);
    }
    if(rect1[2] < rect2[0] && rect1[3] > rect2[1])
    {
        int a = rect2[0] - rect1[2];
        int b = rect1[1] - rect2[3];
        return gip(a, b);
    }
    if(rect1[2] > rect2[0] && rect1[3] > rect2[1])
    {
        int a = rect1[0] - rect2[2];
        int b = rect1[1] - rect2[3];
        return gip(a, b);
    }
    return 0;
}

double prima(double (&arr)[LIM][LIM], int N)
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(arr[i][j] == 0) arr[i][j] = INF;
    vector <double> mindist (N, INF);
    vector <double> dist (N, INF);
    dist[0] = 0;
    vector <bool> used (N, false);
    int ans = 0;
    for (int i = 0; i < N; ++i)
    {
        double min_dist = INF;
        int u;
        for (int j = 0; j < N; ++j)
            if (!used[j] && dist[j] < min_dist)
            {
                min_dist = dist[j];
                u = j;
            }
        ans += min_dist;
        mindist[i] = min_dist;
        used[u] = true;
        for (int v = 0; v < N; ++v)
            dist[v] = min(dist[v], arr[u][v]);
    }
    double max = 0.0;
    for(int i = 0; i < N; i++)
        if(mindist[i] > max) max = mindist[i];
    return max;
}

int main()
{
    int n;
    int rect[LIM][4];
    double mat[LIM][LIM];

    cin >> n;
    /*
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 4; j++)
            cin >> rect[i][j];


    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            mat[i][j] = 0;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j && mat[i][j] == 0)
            {
                mat[i][j] = func(rect[i], rect[j]);
                mat[j][i] = mat[i][j];
            }
    */
    double mas[LIM][LIM];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> mas[i][j];


    printf("%.3f", prima(mas, n));

    cin >> n;
    return 0;
}