#include <bits/stdc++.h> using namespace std; int n; vector<string> graph; vector<vector<int>> g; vector<vector<int>> dist; void bfs(int s) { queue<int> q; q.push(s); dist[s][s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[s][v] == -1) { dist[s][v] = dist[s][u] + 1; q.push(v); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { cin >> n; graph.resize(n); for (int i = 0; i < n; ++i) cin >> graph[i]; g.clear(); g.resize(n + 1); for (int u = 1; u <= n; ++u) { for (int v = 1; v <= n; ++v) { if (u != v && graph[u - 1][v - 1] == '1') { g[u].push_back(v); } } } dist.assign(n + 1, vector<int>(n + 1, -1)); for (int s = 1; s <= n; ++s) bfs(s); int res = INT_MAX; for (int a = 1; a <= n; ++a) { for (int b = a + 1; b <= n; ++b) { int cur = 0; for (int u = 1; u <= n; ++u) { for (int v = 1; v <= n; ++v) { int org = dist[u][v]; int ab = dist[u][a] + dist[b][v]; int ba = dist[u][b] + dist[a][v]; int new_d = min(org, min(ab, ba)); cur = max(cur, new_d); } } res = min(res, cur); } } cout << res << '\n'; } 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 | #include <bits/stdc++.h> using namespace std; int n; vector<string> graph; vector<vector<int>> g; vector<vector<int>> dist; void bfs(int s) { queue<int> q; q.push(s); dist[s][s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[s][v] == -1) { dist[s][v] = dist[s][u] + 1; q.push(v); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { cin >> n; graph.resize(n); for (int i = 0; i < n; ++i) cin >> graph[i]; g.clear(); g.resize(n + 1); for (int u = 1; u <= n; ++u) { for (int v = 1; v <= n; ++v) { if (u != v && graph[u - 1][v - 1] == '1') { g[u].push_back(v); } } } dist.assign(n + 1, vector<int>(n + 1, -1)); for (int s = 1; s <= n; ++s) bfs(s); int res = INT_MAX; for (int a = 1; a <= n; ++a) { for (int b = a + 1; b <= n; ++b) { int cur = 0; for (int u = 1; u <= n; ++u) { for (int v = 1; v <= n; ++v) { int org = dist[u][v]; int ab = dist[u][a] + dist[b][v]; int ba = dist[u][b] + dist[a][v]; int new_d = min(org, min(ab, ba)); cur = max(cur, new_d); } } res = min(res, cur); } } cout << res << '\n'; } return 0; } |