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

// #define int long long

using namespace std;

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		vector<vector<int>> dist(n, vector<int>(n, 99999));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				char c;
				cin >> c;
				if (i == j)
					dist[i][j] = 0;
				else if (c == '1')
					dist[i][j] = 1;
			}
		}

		for (int k = 0; k < n; k++)
		{
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k]);
				}
			}
		}

		int minTotalnie = 99999;
		for (int t1 = 0; t1 < n; t1++)
		{
			for (int t2 = t1 + 1; t2 < n; t2++)
			{
				int maxTutaj = 0;
				for (int a = 0; a < n; a++)
				{
					for (int b = a + 1; b < n; b++)
					{
						int newDist = min(min(dist[a][b], dist[t1][a] + dist[t2][b]), dist[t1][b] + dist[t2][a]);
						maxTutaj = max(maxTutaj, newDist);
					}
				}
				minTotalnie = min(minTotalnie, maxTutaj);
			}
		}
		cout << minTotalnie << endl;
	}
}