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
#include <iostream>
using namespace std;

const int maxN = 400;
const int maxD = maxN + 1;
int d[maxN][maxN];
int dd[maxN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T, n;
    string s;
    cin >> T;
    for(int cs = 0; cs < T; ++cs) {
        cin >> n;
        for(int i = 0; i < n; ++i) {
            cin >> s;
            for(int j = 0; j < n; ++j) d[i][j] = i == j ? 0 : (s[j] == '1' ? 1 : maxD);
        }
        for(int k = 0; k < n; ++k) {
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        int best = maxD;
        for(int ti = 0; ti < n; ++ti) {
            for(int tj = 0; tj < ti; ++tj) {
                for(int i = 0; i < n; ++i) {
                    dd[i] = min(d[ti][i], d[tj][i]);
                }
                int tmx = 0;
                for(int i = 0; i < n; ++i) {
                    for(int j = 0; j < i; ++j) {
                        int td = min(d[i][j], dd[i] + dd[j]);
                        if(td > tmx) {
                            if(td >= best) goto C;
                            tmx = td;
                        }
                    }
                }
                best = min(best, tmx);
C:;
            }
        }
        cout <<  best << endl;
    }
    return 0;
}