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

int main()
{
  int t, n;
  scanf("%i ", &t);
  while (t--)
  {
    scanf("%i ", &n);
    int E[n][n], v = n;
    for (int i = 0; i<n; i++)
    {
      for (int j = 0; j<n; j++) E[i][j] = getchar()=='1'? 1: i==j? 0: n;
      scanf(" ");
    }
    for (int k = 0; k<n; k++) for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) E[i][j] = min(E[i][j], E[i][k]+E[k][j]);
    for (int x = 0; x<n; x++) for (int y = x+1; y<n; y++)
    {
      int T[n], O[n], u = 0;
      for (int k = 0; k<n; k++) T[k] = min(E[x][k], E[k][y]), O[k] = k;
      sort(O, O+n, [&](int a, int b){return T[a]>T[b];});
      for (int i = 0; i<n; i++) for (int j = i+1; j<n; j++)
      {
        if (T[O[i]]+T[O[j]] <= u) break;
        u = max(u, min(T[O[i]]+T[O[j]], E[O[i]][O[j]]));
      }
      v = min(v, u);
    }
    printf("%d\n", v);
  }
  return 0;
}