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
//
//  main.cpp
//  Teleport
//
//  Created by dzmitry kavaliou on 10/03/2025.
//

#include <iostream>
#include <cmath>
using namespace std;
int main(int argc, const char * argv[]) {
    int val[21] = {401};
    int a[400][400];
    int inf = 401;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        int b[400][400];
        int o;
        cin >> o;
        for(int j = 0; j < o; j++){
            for(int p = 0; p < o; p++){
                char c;
                cin >> c;
                a[j][p]=c-48;
                if(j==p) continue;
                else if(a[j][p]==1) continue;
                else a[j][p]=inf;
            }
        }
        for(int k = 0; k < o; k++){
            for(int j = 0; j < o; j++){
                for(int p = j+1; p < o; p++){
                    b[j][p] = min(b[j][p], b[j][k] + b[k][p]);
                    b[p][j] = b[j][p];
                }
            }
        }
        for(int u = 0; u < o; u++){
            for(int l = 0; l < o; l++){
                b[u][l]=a[u][l];
            }
        }
        for(int y = 0; y < o; y++){
            for(int x = y+1; x < o; x++){
                b[y][x]=0;
                b[x][y]=0;
                for(int k = 0; k < o; k++){
                    for(int j = 0; j < o; j++){
                        for(int p = j+1; p < o; p++){
                            b[j][p] = min(b[j][p], b[j][k] + b[k][p]);
                            b[p][j] = b[j][p];
                        }
                    }
                }
                int maxval = 0;
                for(int j = 0; j < o; j++){
                    for(int p = j+1; p < o; p++){
                        maxval = max(maxval, b[j][p]);
                    }
                }
                val[i] = min(maxval, val[i]);
                b[y][x]=a[y][x];
                b[x][y]=a[x][y];
            }
        }
    }
    for(int i = 0; i < t; i++){
        cout << val[i] << endl;
    }
    return 0;
}