// Karol Kosinski 2025 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FR_(i,a,b) for(int i=(a),_b=(b);i<=_b;++i) #define FD_(i,b,a) for(int i=(b),_a=(a);i>=_a;--i) #define ALL(c) (c).begin(),(c).end() #define SIZE(c) int((c).size()) #define X first #define Y second #define endl '\n' #define NAM(x) #x,'=',x using namespace std; using LL = long long; using ULL = unsigned long long; using PII = pair<int, int>; using TIII = tuple<int, int, int>; template<class...T> void _cout(T...a){(cout<<...<<a);} #ifndef ENABLE_DEBUG #define DEB(k,p,f,x...) #else #define DEB(k,p,f,x...) {if(k)_cout("------",setw(4),__LINE__," : ",__FUNCTION__,endl);if(p)f(x);} #endif #define DEBF(f,x...) DEB(1,1,f,x) #define DEBL DEBF(void,0) #define DEBC(p,x...) DEB(0,p,_cout,x) #define DEBUG(x...) DEBC(1,x) constexpr int NX = 405; namespace FloydWarshall { static constexpr int INFTY = 1e9 + 1; int n, D[NX][NX]; void init(int n0) { n = n0; FOR(u,0,n) FOR(v,0,n) D[u][v] = ( u == v ) ? 0 : INFTY; } void add(int u, int v, int w) { D[u][v] = w; } void run() { FOR(k,0,n) FOR(i,0,n) FOR(j,0,n) if ( D[i][j] > D[i][k] + D[k][j] ) D[i][j] = D[i][k] + D[k][j]; } }; void print_fw(int n) { FOR(i,0,n) { DEBUG( "** "); FOR(j,0,n) { DEBUG( FloydWarshall::D[i][j], " " ); } DEBUG(endl); } } void solve() { int n; cin >> n; FloydWarshall::init(n); FOR(i,0,n) { string s; cin >> s; FOR(j,0,n) if ( s[j] == '1' ) { FloydWarshall::add(i, j, 1); FloydWarshall::add(j, i, 1); } } FloydWarshall::run(); auto& S = FloydWarshall::D; DEBF( print_fw, n ); DEBL; int dmax = FloydWarshall::INFTY; FOR(i,0,n) { FOR(j,i+1,n) { int d = 0; FOR(u,0,n) FOR(v,u+1,n) { d = max( d, min( S[u][v], min( S[u][i] + S[j][v], S[u][j] + S[i][v] ) ) ); } dmax = min( dmax, d ); } } cout << dmax << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int z; cin >> z; while ( z -- ) solve(); return 0; }
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 | // Karol Kosinski 2025 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FR_(i,a,b) for(int i=(a),_b=(b);i<=_b;++i) #define FD_(i,b,a) for(int i=(b),_a=(a);i>=_a;--i) #define ALL(c) (c).begin(),(c).end() #define SIZE(c) int((c).size()) #define X first #define Y second #define endl '\n' #define NAM(x) #x,'=',x using namespace std; using LL = long long; using ULL = unsigned long long; using PII = pair<int, int>; using TIII = tuple<int, int, int>; template<class...T> void _cout(T...a){(cout<<...<<a);} #ifndef ENABLE_DEBUG #define DEB(k,p,f,x...) #else #define DEB(k,p,f,x...) {if(k)_cout("------",setw(4),__LINE__," : ",__FUNCTION__,endl);if(p)f(x);} #endif #define DEBF(f,x...) DEB(1,1,f,x) #define DEBL DEBF(void,0) #define DEBC(p,x...) DEB(0,p,_cout,x) #define DEBUG(x...) DEBC(1,x) constexpr int NX = 405; namespace FloydWarshall { static constexpr int INFTY = 1e9 + 1; int n, D[NX][NX]; void init(int n0) { n = n0; FOR(u,0,n) FOR(v,0,n) D[u][v] = ( u == v ) ? 0 : INFTY; } void add(int u, int v, int w) { D[u][v] = w; } void run() { FOR(k,0,n) FOR(i,0,n) FOR(j,0,n) if ( D[i][j] > D[i][k] + D[k][j] ) D[i][j] = D[i][k] + D[k][j]; } }; void print_fw(int n) { FOR(i,0,n) { DEBUG( "** "); FOR(j,0,n) { DEBUG( FloydWarshall::D[i][j], " " ); } DEBUG(endl); } } void solve() { int n; cin >> n; FloydWarshall::init(n); FOR(i,0,n) { string s; cin >> s; FOR(j,0,n) if ( s[j] == '1' ) { FloydWarshall::add(i, j, 1); FloydWarshall::add(j, i, 1); } } FloydWarshall::run(); auto& S = FloydWarshall::D; DEBF( print_fw, n ); DEBL; int dmax = FloydWarshall::INFTY; FOR(i,0,n) { FOR(j,i+1,n) { int d = 0; FOR(u,0,n) FOR(v,u+1,n) { d = max( d, min( S[u][v], min( S[u][i] + S[j][v], S[u][j] + S[i][v] ) ) ); } dmax = min( dmax, d ); } } cout << dmax << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int z; cin >> z; while ( z -- ) solve(); return 0; } |