#include <bits/stdc++.h> using std::cin, std::cout; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; const char endl = '\n'; const int MAX_N = 405; const int INF = INT_MAX / 4; int dist[MAX_N][MAX_N]; // [from][to] bool conn[MAX_N][MAX_N]; struct edge { int a, b; }; void solve() { int n; cin >> n; std::vector<edge> edges; std::string s; for (int a = 0; a < n; a++) { cin >> s; for (int b = 0; b < n; b++) { conn[a][b] = s[b] == '1'; if (a < b) edges.emplace_back(a, b); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) dist[i][j] = 0; else if (conn[i][j]) dist[i][j] = 1; else dist[i][j] = INF; } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[j][k]); } } } int lp1, lp2; int lp = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][j] > lp) { lp = dist[i][j]; lp1 = i; lp2 = j; } } } int prev[MAX_N]; bool visited[MAX_N]{}; std::queue<int> next; next.emplace(lp1); while (not next.empty()) { int curr = next.front(); next.pop(); for (int i = 0; i < n; i++) { if (visited[i]) continue; if (conn[curr][i]) { next.emplace(i); visited[i] = true; prev[i] = curr; } } } std::vector<int> path; int v = lp2; while (v != lp1) { path.emplace_back(v); v = prev[v]; } path.emplace_back(lp1); int min = INT_MAX; for (int t1 : path) { for (int t2 : path) { if (t1 > t2) continue; int max = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { int d = std::min({dist[i][j], dist[i][t1] + dist[t2][j], dist[i][t2] + dist[t1][j]}); if (d > max) max = d; } } if (max < min) min = max; } } cout << min << endl; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; for (int i = 0; i < t; i++) 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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <bits/stdc++.h> using std::cin, std::cout; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; const char endl = '\n'; const int MAX_N = 405; const int INF = INT_MAX / 4; int dist[MAX_N][MAX_N]; // [from][to] bool conn[MAX_N][MAX_N]; struct edge { int a, b; }; void solve() { int n; cin >> n; std::vector<edge> edges; std::string s; for (int a = 0; a < n; a++) { cin >> s; for (int b = 0; b < n; b++) { conn[a][b] = s[b] == '1'; if (a < b) edges.emplace_back(a, b); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) dist[i][j] = 0; else if (conn[i][j]) dist[i][j] = 1; else dist[i][j] = INF; } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[j][k]); } } } int lp1, lp2; int lp = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][j] > lp) { lp = dist[i][j]; lp1 = i; lp2 = j; } } } int prev[MAX_N]; bool visited[MAX_N]{}; std::queue<int> next; next.emplace(lp1); while (not next.empty()) { int curr = next.front(); next.pop(); for (int i = 0; i < n; i++) { if (visited[i]) continue; if (conn[curr][i]) { next.emplace(i); visited[i] = true; prev[i] = curr; } } } std::vector<int> path; int v = lp2; while (v != lp1) { path.emplace_back(v); v = prev[v]; } path.emplace_back(lp1); int min = INT_MAX; for (int t1 : path) { for (int t2 : path) { if (t1 > t2) continue; int max = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { int d = std::min({dist[i][j], dist[i][t1] + dist[t2][j], dist[i][t2] + dist[t1][j]}); if (d > max) max = d; } } if (max < min) min = max; } } cout << min << endl; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; for (int i = 0; i < t; i++) solve(); return 0; } |