#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define piii pair<int, pair<int, int>> #define st first #define nd second.first #define rd second.second #define For(i, l, r) for (int i = l; i <= r; i++) #define Forcin(l, r, a) \ for (int i = l; i <= r; i++) \ cin >> a[i]; #define Ford(i, l, r) for (int i = l; i >= r; i--) #define ben(v) v.begin(), v.end() #define LOCAL 0 #define LOCAL2 0 using namespace std; const int M = 400005, inf = 1e9; bool comp(piii a, piii b) { if (a.st != b.st) return a.st > b.st; return a.second < b.second; } void solve() { int n; cin >> n; n++; vector<vector<bool>> adjacency_matrix(n, vector<bool>(n, 0)); vector<vector<int>> graph(n); vector<vector<int>> distances(n); n--; For(i, 1, n) { string w; cin >> w; w = "#" + w; For(j, 1, n) { if (w[j] == '1') { graph[i].push_back(j); adjacency_matrix[i][j] = 1; } } } For(i, 1, n) { vector<int> distance(n + 1, inf); queue<pii> q; q.push({i, 0}); while (!q.empty()) { auto [v, d] = q.front(); q.pop(); if (d >= distance[v]) continue; distance[v] = d; for (auto u : graph[v]) { q.push({u, d + 1}); } } distances[i] = distance; } vector<piii> dists; For(i, 1, n) For(j, i + 1, n) dists.push_back({distances[i][j], {i, j}}); sort(ben(dists), comp); int best = 0, ac = 1; pii added = {0, 0}; For(i, 1, n) For(j, i + 1, n) best = max(best, distances[i][j]); for (auto tel : dists) { auto [a, b] = tel.second; int maxi = 0; for (auto el : dists) { auto [u, v] = el.second; maxi = max(maxi, min(el.st, min(distances[a][u] + distances[b][v], distances[b][u] + distances[a][v]))); if (maxi >= best) break; } if (maxi < best) { best = maxi; added = {a, b}; ac = 1; } } cout << best << '\n'; } signed main() { cin.tie(0)->sync_with_stdio(); if (LOCAL) freopen("moje/15.in", "r", stdin); if (LOCAL2) freopen("local_out.txt", "w", stdout); int t; cin >> t; while (t--) solve(); }
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 | #include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define piii pair<int, pair<int, int>> #define st first #define nd second.first #define rd second.second #define For(i, l, r) for (int i = l; i <= r; i++) #define Forcin(l, r, a) \ for (int i = l; i <= r; i++) \ cin >> a[i]; #define Ford(i, l, r) for (int i = l; i >= r; i--) #define ben(v) v.begin(), v.end() #define LOCAL 0 #define LOCAL2 0 using namespace std; const int M = 400005, inf = 1e9; bool comp(piii a, piii b) { if (a.st != b.st) return a.st > b.st; return a.second < b.second; } void solve() { int n; cin >> n; n++; vector<vector<bool>> adjacency_matrix(n, vector<bool>(n, 0)); vector<vector<int>> graph(n); vector<vector<int>> distances(n); n--; For(i, 1, n) { string w; cin >> w; w = "#" + w; For(j, 1, n) { if (w[j] == '1') { graph[i].push_back(j); adjacency_matrix[i][j] = 1; } } } For(i, 1, n) { vector<int> distance(n + 1, inf); queue<pii> q; q.push({i, 0}); while (!q.empty()) { auto [v, d] = q.front(); q.pop(); if (d >= distance[v]) continue; distance[v] = d; for (auto u : graph[v]) { q.push({u, d + 1}); } } distances[i] = distance; } vector<piii> dists; For(i, 1, n) For(j, i + 1, n) dists.push_back({distances[i][j], {i, j}}); sort(ben(dists), comp); int best = 0, ac = 1; pii added = {0, 0}; For(i, 1, n) For(j, i + 1, n) best = max(best, distances[i][j]); for (auto tel : dists) { auto [a, b] = tel.second; int maxi = 0; for (auto el : dists) { auto [u, v] = el.second; maxi = max(maxi, min(el.st, min(distances[a][u] + distances[b][v], distances[b][u] + distances[a][v]))); if (maxi >= best) break; } if (maxi < best) { best = maxi; added = {a, b}; ac = 1; } } cout << best << '\n'; } signed main() { cin.tie(0)->sync_with_stdio(); if (LOCAL) freopen("moje/15.in", "r", stdin); if (LOCAL2) freopen("local_out.txt", "w", stdout); int t; cin >> t; while (t--) solve(); } |