1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
int t,n;
char m;
int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    std::cin>>t;
    for(int test=0;test<t;test++){
        std::cin>>n;
        std::vector<std::vector<int>> odl(n);
        
        std::vector<int> odl_tel(n);
        for(int i=0;i<n;i++){
            odl[i].resize(n,n);
        for(int j=0;j<n;j++){
            std::cin>>m;
            if(m=='1')
                odl[i][j]=1;
            else
            if(i==j)
                odl[i][j]=0;
                
        }
        }
        for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            odl[i][j]=std::min(odl[i][j],odl[i][k]+odl[k][j]);
        int best=n;
        int s1=0;
        int s2=0;
        int ttt=0;
        std::set<std::pair<int,int> >tes;
        for(int te1=0;te1<n;te1++)
        for(int te2=te1+1;te2<n;te2++)
        {
            int act=0;
            bool fail=false;
            for(int i=0;i<n;i++){
                odl_tel[i]=std::min(odl[i][te1],odl[i][te2]);
            }
            for(auto x:tes)
            if(std::min(odl[x.first][x.second],odl_tel[x.first]+odl_tel[x.second])>=best)
                fail=true;
            if(!fail){
                ttt++;
            /*for(int m1=0;m1<sho.size();m1++)
                for(int m2=m1+1;m2<sho.size();m2++){
                    int od=std::min(odl[sho[m1]][sho[m2]],odl_tel[sho[m1]]+odl_tel[sho[m2]]);
                    if(act<od)
                        act=od;
                    if(act>=best){
                        m2=sho.size();
                        m1=sho.size();
                        fail=true;
                    }
                }*/
            //std::cerr<<best<<" "<<sho.size()<<" "<<fail<<std::endl;
            
            for(int m1=0;m1<n;m1++)
                for(int m2=m1+1;m2<n;m2++){
                    int od=std::min(odl[m1][m2],odl_tel[m1]+odl_tel[m2]);
                    if(act<od)
                        act=od;
                    if(act>=best){
                        tes.emplace(m1,m2);
                        m2=n;
                        m1=n;
                    }
                }
            if(act<=best){
                best=act;
                
            }
                //std::cerr<<te1<<" "<<te2<<std::endl;
            }
        }
        //std::cerr<<ttt<<" "<<tes.size()<<std::endl;
        std::cout<<best<<"\n";
    }
}