#define debug 0 #include <bits/stdc++.h> #define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define perf 1 #define st first #define nd second #define remin(a,b) a=min(a,b); #define remax(a,b) a=max(a,b); #define mod 998244353 //#define mod 1'000'000'007 using namespace std; const int inf = 1e8; int n; vector<vector<int>> m, kra, dist, rdist; void bfs(int source) { dist[source][source] = 0; queue<int> q; q.push(source); while (!q.empty()) { int cur = q.front(); q.pop(); for (int next : kra[cur]) { if (dist[source][next] == inf) { dist[source][next] = dist[source][cur] + 1; q.push(next); } } } } void solve() { cin >> n; m.assign(n, vector<int>(n)); dist.assign(n, vector<int>(n, inf)); rdist.assign(n, vector<int>(n, inf)); kra.assign(n, {}); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { char c; cin >> c; m[i][j] = c - '0'; if (m[i][j] == 1) { kra[i].emplace_back(j); } } } //do a bfs for every source for (int i = 0; i < n; ++i) bfs(i); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { rdist[i][j] = min(dist[i][j], max(dist[i][0], dist[0][j])); //real dist, bo mozemy tankowac } } if (debug) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cerr << rdist[i][j] << ' '; } cerr << '\n'; } } int ans = inf; for (int u = 0; u < n; ++u) { for (int v = 0; v < n; ++v) { //tunel pomiedzy u-v //przetestuj kazde polaczenie int mx = -inf; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int path=inf; remin(path, rdist[i][j]); //bez tunely remin(path, max(rdist[i][u], rdist[v][j])); //z tunelem remax(mx, path); } } remin(ans, mx); } } cout << ans << '\n'; } int main() { fastio(); int t=1; cin >> t; while (t--) { 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 | #define debug 0 #include <bits/stdc++.h> #define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define perf 1 #define st first #define nd second #define remin(a,b) a=min(a,b); #define remax(a,b) a=max(a,b); #define mod 998244353 //#define mod 1'000'000'007 using namespace std; const int inf = 1e8; int n; vector<vector<int>> m, kra, dist, rdist; void bfs(int source) { dist[source][source] = 0; queue<int> q; q.push(source); while (!q.empty()) { int cur = q.front(); q.pop(); for (int next : kra[cur]) { if (dist[source][next] == inf) { dist[source][next] = dist[source][cur] + 1; q.push(next); } } } } void solve() { cin >> n; m.assign(n, vector<int>(n)); dist.assign(n, vector<int>(n, inf)); rdist.assign(n, vector<int>(n, inf)); kra.assign(n, {}); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { char c; cin >> c; m[i][j] = c - '0'; if (m[i][j] == 1) { kra[i].emplace_back(j); } } } //do a bfs for every source for (int i = 0; i < n; ++i) bfs(i); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { rdist[i][j] = min(dist[i][j], max(dist[i][0], dist[0][j])); //real dist, bo mozemy tankowac } } if (debug) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cerr << rdist[i][j] << ' '; } cerr << '\n'; } } int ans = inf; for (int u = 0; u < n; ++u) { for (int v = 0; v < n; ++v) { //tunel pomiedzy u-v //przetestuj kazde polaczenie int mx = -inf; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int path=inf; remin(path, rdist[i][j]); //bez tunely remin(path, max(rdist[i][u], rdist[v][j])); //z tunelem remax(mx, path); } } remin(ans, mx); } } cout << ans << '\n'; } int main() { fastio(); int t=1; cin >> t; while (t--) { solve(); } return 0; } |