#include<bits/stdc++.h> //#pragma GCC optimize("O3") using namespace std; const int inf = 1e9; bool okay(int n, vector<vector<int>> &odl, int cel){ vector<vector<int>> pomoc(n, vector<int>(n)); // Jeśli i to ten dalszy teleporter od j, to pomoc[i][j] oznacza najdalszą odległość w jakiej może być drugi teleporter od i. for(int i=0;i<n; i++){ for(int j=0; j<n; j++){ int najdalsza = 0; for(int k=0; k<n; k++){ if(odl[j][k] > cel){ najdalsza = max(najdalsza, odl[i][k]); } } pomoc[i][j] = cel - najdalsza; } } for(int uno = 0; uno<n; uno++){ for(int dos = 0; dos < n; dos++){ bool dasie = 1; for(int i=0; i<n; i++){ if(odl[i][uno] > cel && odl[i][dos]>cel) dasie=0; if(odl[i][uno]>=odl[i][dos]){ if(odl[i][dos] > pomoc[uno][i]){ dasie = 0; break; } } else{ if(odl[i][uno] > pomoc[dos][i]){ dasie =0; break; } } } if(dasie) return 1; } } return 0; } void solve(){ int n; cin >> n; vector<vector<bool>> gra(n, vector<bool>(n)); vector<vector<int>> odl(n, vector<int>(n, inf)); string s; for(int i=0; i<n; i++){ cin >> s; for(int j=0; j<n; j++){ if(s[j]=='1'){ gra[i][j]=1; } } } for(int i=0; i<n; i++){ queue<int> bfs; odl[i][i]=0; bfs.push(i); while(!bfs.empty()){ int aktu = bfs.front(); bfs.pop(); for(int j=0; j<n; j++){ if(odl[i][j] == inf){ if(gra[aktu][j]){ odl[i][j] = odl[i][aktu]+1; bfs.push(j); } } } } } int l = 0, r = n; while(l<r){ int m = (l+r)/2; if(okay(n, odl, m)){ r = m; } else{ l = m+1; } } cout << l << "\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 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 | #include<bits/stdc++.h> //#pragma GCC optimize("O3") using namespace std; const int inf = 1e9; bool okay(int n, vector<vector<int>> &odl, int cel){ vector<vector<int>> pomoc(n, vector<int>(n)); // Jeśli i to ten dalszy teleporter od j, to pomoc[i][j] oznacza najdalszą odległość w jakiej może być drugi teleporter od i. for(int i=0;i<n; i++){ for(int j=0; j<n; j++){ int najdalsza = 0; for(int k=0; k<n; k++){ if(odl[j][k] > cel){ najdalsza = max(najdalsza, odl[i][k]); } } pomoc[i][j] = cel - najdalsza; } } for(int uno = 0; uno<n; uno++){ for(int dos = 0; dos < n; dos++){ bool dasie = 1; for(int i=0; i<n; i++){ if(odl[i][uno] > cel && odl[i][dos]>cel) dasie=0; if(odl[i][uno]>=odl[i][dos]){ if(odl[i][dos] > pomoc[uno][i]){ dasie = 0; break; } } else{ if(odl[i][uno] > pomoc[dos][i]){ dasie =0; break; } } } if(dasie) return 1; } } return 0; } void solve(){ int n; cin >> n; vector<vector<bool>> gra(n, vector<bool>(n)); vector<vector<int>> odl(n, vector<int>(n, inf)); string s; for(int i=0; i<n; i++){ cin >> s; for(int j=0; j<n; j++){ if(s[j]=='1'){ gra[i][j]=1; } } } for(int i=0; i<n; i++){ queue<int> bfs; odl[i][i]=0; bfs.push(i); while(!bfs.empty()){ int aktu = bfs.front(); bfs.pop(); for(int j=0; j<n; j++){ if(odl[i][j] == inf){ if(gra[aktu][j]){ odl[i][j] = odl[i][aktu]+1; bfs.push(j); } } } } } int l = 0, r = n; while(l<r){ int m = (l+r)/2; if(okay(n, odl, m)){ r = m; } else{ l = m+1; } } cout << l << "\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ solve(); } } |