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
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        vector<string> graf(n);
        for(int i = 0; i < n; i++) cin >> graf[i];
        const int INF = 1e9;
        vector<vector<int>> odl(n, vector<int>(n, INF));
        for(int i = 0; i < n; i++){
            deque<int> dq;
            odl[i][i] = 0;
            dq.push_back(i);
            while(!dq.empty()){
                int u = dq.front();
                dq.pop_front();
                for(int v = 0; v < n; v++){
                    if(graf[u][v] == '1' && odl[i][v] > odl[i][u] + 1){
                        odl[i][v] = odl[i][u] + 1;
                        dq.push_back(v);
                    }
                }
            }
        }
        int D0 = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                D0 = max(D0, odl[i][j]);
        int wynik = D0;
        for(int u = 0; u < n; u++){
            for(int v = u + 1; v < n; v++){
                vector<int> a(n);
                for(int i = 0; i < n; i++)
                    a[i] = min(odl[i][u], odl[i][v]);
                int cur = 0;
                for(int x = 0; x < n; x++){
                    for(int y = 0; y < n; y++){
                        int cand = min(odl[x][y], a[x] + a[y]);
                        cur = max(cur, cand);
                        if(cur >= wynik) break;
                    }
                    if(cur >= wynik) break;
                }
                wynik = min(wynik, cur);
                if(wynik == 0) break;
            }
            if(wynik == 0) break;
        }
        cout << wynik << "\n";
    }
    return 0;
}