#include <bits/stdc++.h> using namespace std; const int N = 4e2 + 5; const int INF = 1e9; string Matrix[N]; int Dist[N][N]; void FloydWarshall(int n) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { Dist[i][j] = INF; if(Matrix[i][j] == '1') Dist[i][j] = 1; else if(i == j) Dist[i][j] = 0; } } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]); } } } } int Solve(int n) { int sol = INF; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { int cur = 0; for(int v1 = 1; v1 <= n; v1++) { for(int v2 = v1+1; v2 <= n; v2++) cur = max(cur, min({Dist[v1][v2], Dist[v1][i] + Dist[j][v2], Dist[v1][j] + Dist[i][v2]})); } sol = min(sol, cur); } } return sol; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t, n; cin >> t; while(t --> 0) { cin >> n; for(int i = 1; i <= n; i++) { cin >> Matrix[i]; Matrix[i] = "0" + Matrix[i]; } FloydWarshall(n); cout << Solve(n) << "\n"; } }
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 | #include <bits/stdc++.h> using namespace std; const int N = 4e2 + 5; const int INF = 1e9; string Matrix[N]; int Dist[N][N]; void FloydWarshall(int n) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { Dist[i][j] = INF; if(Matrix[i][j] == '1') Dist[i][j] = 1; else if(i == j) Dist[i][j] = 0; } } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]); } } } } int Solve(int n) { int sol = INF; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { int cur = 0; for(int v1 = 1; v1 <= n; v1++) { for(int v2 = v1+1; v2 <= n; v2++) cur = max(cur, min({Dist[v1][v2], Dist[v1][i] + Dist[j][v2], Dist[v1][j] + Dist[i][v2]})); } sol = min(sol, cur); } } return sol; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t, n; cin >> t; while(t --> 0) { cin >> n; for(int i = 1; i <= n; i++) { cin >> Matrix[i]; Matrix[i] = "0" + Matrix[i]; } FloydWarshall(n); cout << Solve(n) << "\n"; } } |