#include <bits/stdc++.h> using namespace std; void solve(){ int n; cin >> n; vector<vector<int>> adj(n,vector<int>(n)); for (int i = 0; i<n; i++){ char c; for (int j = 0; j<n; j++){ cin >> c; adj[i][j]=c-'0'; } } vector<vector<int>> odl(n,vector<int>(n)); vector<vector<bitset<400>>> bs(n,vector<bitset<400>>(n)); vector<int> vis(n); int iter=0; int mn=1; for (int i = 0; i<n; i++){ queue<int> q; q.push(i); vis[i]=++iter; while(q.size()){ int v = q.front(); q.pop(); bs[i][odl[i][v]][v]=1; for (int j = 0; j<n; j++){ if (adj[v][j] && vis[j]!=iter){ vis[j]=iter; q.push(j); odl[i][j]=odl[i][v]+1; mn=max(mn,odl[i][j]); } } } for (int j = n-2; j>=0; j--)bs[i][j]|=bs[i][j+1]; } for (int A = 0; A<n; A++){ for (int B = A+1; B<n; B++){ vector<bitset<400>> tmp(n); for (int i = 0; i<n; i++)tmp[i]=bs[A][i]&bs[B][i]; int mx=0; for (int C = 0; C<n && mx<mn; C++){ int d=min(odl[A][C],odl[B][C]); int l=mx,p=mn,md; while(l<p){ md=(l+p+1)/2; if ((bs[C][md]&tmp[max(md-d,0)]).none())p=md-1; else l=md; } mx=max(mx,l); } mn=min(mn,mx); } } cout << mn << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); 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 | #include <bits/stdc++.h> using namespace std; void solve(){ int n; cin >> n; vector<vector<int>> adj(n,vector<int>(n)); for (int i = 0; i<n; i++){ char c; for (int j = 0; j<n; j++){ cin >> c; adj[i][j]=c-'0'; } } vector<vector<int>> odl(n,vector<int>(n)); vector<vector<bitset<400>>> bs(n,vector<bitset<400>>(n)); vector<int> vis(n); int iter=0; int mn=1; for (int i = 0; i<n; i++){ queue<int> q; q.push(i); vis[i]=++iter; while(q.size()){ int v = q.front(); q.pop(); bs[i][odl[i][v]][v]=1; for (int j = 0; j<n; j++){ if (adj[v][j] && vis[j]!=iter){ vis[j]=iter; q.push(j); odl[i][j]=odl[i][v]+1; mn=max(mn,odl[i][j]); } } } for (int j = n-2; j>=0; j--)bs[i][j]|=bs[i][j+1]; } for (int A = 0; A<n; A++){ for (int B = A+1; B<n; B++){ vector<bitset<400>> tmp(n); for (int i = 0; i<n; i++)tmp[i]=bs[A][i]&bs[B][i]; int mx=0; for (int C = 0; C<n && mx<mn; C++){ int d=min(odl[A][C],odl[B][C]); int l=mx,p=mn,md; while(l<p){ md=(l+p+1)/2; if ((bs[C][md]&tmp[max(md-d,0)]).none())p=md-1; else l=md; } mx=max(mx,l); } mn=min(mn,mx); } } cout << mn << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--)solve(); } |