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
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
  #include <iostream>
  #include <stdio.h>
  #include <cstdio>
  using namespace std;

  int t, n;

  int distanceSize = 0;
  int dist[400][400];
  int connection[400 * 400][3];
  int nConnections = 0;

  void swapConnections(int conA, int conB) {
    if(conA == conB) {
      return;
    }
    int a = connection[conA][0];
    int b = connection[conA][1];
    int c = connection[conA][2];
    connection[conA][0] = connection[conB][0];
    connection[conA][1] = connection[conB][1];
    connection[conA][2] = connection[conB][2];
    connection[conB][0] = a;
    connection[conB][1] = b;
    connection[conB][2] = c;
  }
  
  void sortConnections(int iLeftConnection, int iRightConnection) {
    if(iLeftConnection >= iRightConnection) {
      return;
    }
    int insertion = iLeftConnection;
    int pivot = connection[iRightConnection][2];
    for(int current = insertion; current <= iRightConnection; current++) {
      if(connection[current][2] >= pivot) {
        //cerr << "swap " << current << " " << insertion << endl;
        swapConnections(current, insertion);
        insertion++;
      }
    }
    sortConnections(iLeftConnection, insertion - 2);
    // insertion - 1 is at correct place
    sortConnections(insertion, iRightConnection);
  }

  int calculateMaxDistance(int iTeleportConnection, int teleportMaxDistance) {
    int maxDistance = 0;
    for (int iConnection = 0; iConnection < nConnections; iConnection++) {
      int directDistance = dist[connection[iConnection][0]][connection[iConnection][1]];
      int teleportDistanceA = dist[connection[iConnection][0]][connection[iTeleportConnection][0]]
          + dist[connection[iConnection][1]][connection[iTeleportConnection][1]];
      int teleportDistanceB = dist[connection[iConnection][0]][connection[iTeleportConnection][1]]
          + dist[connection[iConnection][1]][connection[iTeleportConnection][0]];
      int teleportDistance = min(teleportDistanceA, teleportDistanceB);
      int minDistance = min(directDistance, teleportDistance);
      maxDistance = max(maxDistance, minDistance);
      if(maxDistance >= teleportMaxDistance) {
        return teleportMaxDistance;
      }
    }
    return maxDistance;
  }

  void solveOneCase() {
    // read input
    cin >> n;
    getchar();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dist[i][j] = getchar() - '0';
        if (i != j && dist[i][j] == 0) {
          dist[i][j] = 1000;
        }
      }
      getchar();
    }

    // calculate distance
    for (int newCity = 0; newCity < n; newCity++) {
      for (int cityA = 0; cityA < newCity; cityA++) {
        for (int cityB = 0; cityB < newCity; cityB++) {
          // cityB -- cityA -- newCity
          int distanceDirect = dist[cityB][newCity];
          int distanceThroughCityAToB = dist[cityB][cityA] + dist[cityA][newCity];
          int shortest = min(distanceDirect, distanceThroughCityAToB);
          dist[cityB][newCity] = shortest;
          dist[newCity][cityB] = shortest;
        }
      }
      for (int cityA = 0; cityA < newCity; cityA++) {
        for (int cityB = 0; cityB < newCity; cityB++) {
          // cityB -- newCity -- cityA
          int distanceDirect = dist[cityB][cityA];
          int distanceThroughNewCity = dist[cityB][newCity] + dist[newCity][cityA];
          int shortest = min(distanceDirect, distanceThroughNewCity);
          dist[cityB][cityA] = shortest;
          dist[cityA][cityB] = shortest;
        }
      }
    }
    
    // prepare connections
    for (int cityA = 0; cityA < n; cityA++) {
      for (int cityB = cityA; cityB < n; cityB++) {
        connection[nConnections][0] = cityA;
        connection[nConnections][1] = cityB;
        connection[nConnections][2] = dist[cityA][cityB];
        nConnections++;
      }
    }
    
    // sort connections
    sortConnections(0, nConnections - 1);

    // check teleports
    int directMaxDistance = connection[0][2];
    int teleportMaxDistance = directMaxDistance;
    for (int iTeleportConnection = 0; iTeleportConnection < nConnections; iTeleportConnection++) {
      if (connection[iTeleportConnection][2] <= directMaxDistance - teleportMaxDistance) {
        // teleport cannot reduce distance more than its own length
        break;
      }
      int teleportDistance = calculateMaxDistance(iTeleportConnection, teleportMaxDistance);
      teleportMaxDistance = min(teleportDistance, teleportMaxDistance);
    }

    cout << teleportMaxDistance << endl;
  }

  int main() {
    cin >> t;
    for (int i = 0; i < t; i++) {
      solveOneCase();
    }
    return 0;
  }