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
#include <stdio.h>
#include <vector>
using namespace std;

const int inf = 1013;

int main() {
  int tt; 
	scanf("%d", &tt);
	while (tt--) {
		int n;
		scanf("%d", &n);
		char a[413];
		int t[413][413], c[413];
		for (int i = 0; i < n; i++) {
			scanf("%s", a);
			for (int j = 0; j < n; j++) if (a[j] == '1') t[i][j] = 1; else t[i][j] = inf;
			t[i][i] = 0;
		}
		for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
			t[i][j] = std::min(t[i][j], t[i][k] + t[k][j]);
		}
		int ret = inf;
		for (int x = 0; x < n; x++) for (int y = x+1; y < n; y++) {
			for (int i = 0; i < n; i++) c[i] = std::min(t[x][i], t[y][i]);
			int w = 0;
			for (int i = 0; i < n; i++) {
				for (int j = i+1; j < n; j++) 
					if(c[i] + c[j] > w)
						w = std::max(w, std::min(t[i][j], c[i]+c[j]));
				if (w >= ret) break;
			}
			ret = std::min(ret, w);
		}
		printf("%d\n", ret);
	}
	return 0;
}