#include <stdio.h>#include <string>#include <stack>#include <vector>#include <string.h>#include <algorithm>using namespace std;vector<int> g1[55];vector<int> g2[55];class HardProof{    int n;    int G[55][55];    int a[55*55],aNum;    void dfs(int u,int f[],vector<int> g[55])    {        if(f[u]) return;        f[u]=1;        for(int i=0;i<(int)g[u].size();++i)        {            int v=g[u][i];            dfs(v,f,g);        }    }    int check(int M)    {        for(int i=1;i<=aNum;++i)        {            const int S=a[i];            for(int i=0;i<n;++i) g1[i].clear(),g2[i].clear();            for(int i=0;i<n;++i) {                for(int j=0;j<n;++j) {                    if(i!=j&&S<=G[i][j]&&G[i][j]<=S+M) {                        g1[i].push_back(j);                        g2[j].push_back(i);                    }                }            }            int f1[55],f2[55];            memset(f1,0,sizeof(f1));            memset(f2,0,sizeof(f2));            dfs(0,f1,g1);            dfs(0,f2,g2);            for(int i=0;i<n;++i) {                if(!f1[i]||!f2[i]) break;                if(i==n-1) return 1;            }        }        return 0;    }public:	int minimumCost(vector<int> D)	{	    n=1;	    while(n*n!=(int)D.size()) ++n;	    if(1==n) return 0;	    int low=150000,high=0;	    aNum=0;	    for(int i=0;i<n;++i) {            for(int j=0;j<n;++j) if(i!=j) {                int p=D[i*n+j];                if(p<low) low=p;                if(p>high) high=p;                G[i][j]=p;                a[++aNum]=p;            }	    }        sort(a+1,a+aNum+1);        aNum=unique(a+1,a+aNum+1)-(a+1);        high=high-low;        low=0;        int ans=high;        while(low<=high)        {            int M=(low+high)>>1;            if(check(M)) ans=min(ans,M),high=M-1;            else low=M+1;        }        return ans;	}};