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
#include <climits>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int NIESKONCZONOSC = INT_MAX;

// Dijkstra, ale trochę na opak
vector<int> dijkstra(int skad, const vector<vector<int>> &mapaDrog,
                     int liczbaMiast) {
  vector<int> odleglosc(liczbaMiast, NIESKONCZONOSC);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>>
      kolejkaPierwszenstwa;

  odleglosc[skad] = 0;
  kolejkaPierwszenstwa.push({0, skad});

  while (!kolejkaPierwszenstwa.empty()) {
    int koszt = kolejkaPierwszenstwa.top().first;
    int miasto = kolejkaPierwszenstwa.top().second;
    kolejkaPierwszenstwa.pop();

    if (koszt > odleglosc[miasto])
      continue;

    for (int sasiad = 0; sasiad < liczbaMiast; ++sasiad) {
      if (mapaDrog[miasto][sasiad] == 1) { // Istnieje droga
        int nowyKoszt = odleglosc[miasto] + 1;
        if (nowyKoszt < odleglosc[sasiad]) {
          odleglosc[sasiad] = nowyKoszt;
          kolejkaPierwszenstwa.push({nowyKoszt, sasiad});
        }
      }
    }
  }

  return odleglosc;
}

// Znajdujemy największą minimalną odległość (tzw. "maksymalna dziwność miasta")
// :p
int znajdzMaksDziwnosc(const vector<vector<int>> &mapaDrog, int liczbaMiast) {
  int maksOdleglosc = 0;

  for (int i = 0; i < liczbaMiast; ++i) {
    vector<int> odleglosci = dijkstra(i, mapaDrog, liczbaMiast);
    for (int j = 0; j < liczbaMiast; ++j) {
      if (odleglosci[j] < NIESKONCZONOSC) {
        maksOdleglosc = max(maksOdleglosc, odleglosci[j]);
      }
    }
  }

  return maksOdleglosc;
}

// Główna funkcja rozwiązująca problem
int rozwiazPrzypadek(int liczbaMiast, const vector<vector<int>> &mapaDrog) {
  int oryginalnaDziwnosc = znajdzMaksDziwnosc(mapaDrog, liczbaMiast);

  // Szukamy najbardziej odjechanego miasta
  vector<int> odleglosciZPierwszego = dijkstra(0, mapaDrog, liczbaMiast);
  int najbardziejOdlegleMiasto = 0;
  for (int i = 1; i < liczbaMiast; ++i) {
    if (odleglosciZPierwszego[i] >
        odleglosciZPierwszego[najbardziejOdlegleMiasto]) {
      najbardziejOdlegleMiasto = i;
    }
  }
  // Szukamy najbardziej odjechanego miasta
  vector<int> odleglosciOdNajdalszego =
      dijkstra(najbardziejOdlegleMiasto, mapaDrog, liczbaMiast);
  int drugieNajdalszeMiasto = najbardziejOdlegleMiasto;
  for (int i = 0; i < liczbaMiast; ++i) {
    if (odleglosciOdNajdalszego[i] >
        odleglosciOdNajdalszego[drugieNajdalszeMiasto]) {
      drugieNajdalszeMiasto = i;
    }
  }

  // Robimy czary-mary i dodajemy teleport!
  vector<vector<int>> nowaMapa = mapaDrog;
  nowaMapa[najbardziejOdlegleMiasto][drugieNajdalszeMiasto] = 1;
  nowaMapa[drugieNajdalszeMiasto][najbardziejOdlegleMiasto] = 1;

  // Patrzymy, czy teleport pomógł
  int nowaDziwnosc = znajdzMaksDziwnosc(nowaMapa, liczbaMiast);

  // Zwracamy minimalny możliwy rozmiar baku po optymalnym dodaniu teleportu
  return nowaDziwnosc;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
//zapomniałem o tym...
  int ileTestow;
  cin >> ileTestow;
  vector<int> wyniki;

  while (ileTestow--) {
    int liczbaMiast;
    cin >> liczbaMiast;
    vector<vector<int>> mapaDrog(liczbaMiast, vector<int>(liczbaMiast));

    for (int i = 0; i < liczbaMiast; ++i) {
      string linia;
      cin >> linia;
      for (int j = 0; j < liczbaMiast; ++j) {
        mapaDrog[i][j] = (linia[j] - '0'); // Zamiana '0' lub '1' na int
      }
    }

    wyniki.push_back(rozwiazPrzypadek(liczbaMiast, mapaDrog));
  }

  // Wypisujemy nasze mądre obliczenia!
  for (auto wynik : wyniki) {
    cout << wynik << "\n";
  }

  return 0;
}