//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; typedef pair<int, int> T; const int oo = 1e9+7; void solve(){ int n; cin >> n; vector d(n+1, vector<int>(n+1, oo)); for (int i = 1; i<=n; i++) d[i][i] = 0; for (int i = 1; i<=n; i++){ for (int j = 1; j<=n; j++){ char c; cin >> c; if (c == '1') { d[i][j] = 1; } } } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } int ans = oo; for (int u = 1; u <= n; u++){ for (int v = 1; v <= n; v++){ int curr = 0; for (int i = 1; i<=n; i++){ for (int j = 1; j<=n; j++){ curr = max(curr, min({d[i][j], d[i][u] + d[v][j], d[i][v] + d[u][j]})); } } ans = min(ans, curr); } } cout << ans << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 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 | //Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; typedef pair<int, int> T; const int oo = 1e9+7; void solve(){ int n; cin >> n; vector d(n+1, vector<int>(n+1, oo)); for (int i = 1; i<=n; i++) d[i][i] = 0; for (int i = 1; i<=n; i++){ for (int j = 1; j<=n; j++){ char c; cin >> c; if (c == '1') { d[i][j] = 1; } } } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } int ans = oo; for (int u = 1; u <= n; u++){ for (int v = 1; v <= n; v++){ int curr = 0; for (int i = 1; i<=n; i++){ for (int j = 1; j<=n; j++){ curr = max(curr, min({d[i][j], d[i][u] + d[v][j], d[i][v] + d[u][j]})); } } ans = min(ans, curr); } } cout << ans << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) solve(); return 0; } |