#include <cstdio> #include <algorithm> using namespace std; int main() { int t, n; scanf("%i ", &t); while (t--) { scanf("%i ", &n); int E[n][n], v = n; for (int i = 0; i<n; i++) { for (int j = 0; j<n; j++) E[i][j] = getchar()=='1'? 1: i==j? 0: n; scanf(" "); } for (int k = 0; k<n; k++) for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) E[i][j] = min(E[i][j], E[i][k]+E[k][j]); for (int x = 0; x<n; x++) for (int y = x+1; y<n; y++) { int T[n], O[n], u = 0; for (int k = 0; k<n; k++) T[k] = min(E[x][k], E[k][y]), O[k] = k; sort(O, O+n, [&](int a, int b){return T[a]>T[b];}); for (int i = 0; i<n; i++) for (int j = i+1; j<n; j++) { if (T[O[i]]+T[O[j]] <= u) break; u = max(u, min(T[O[i]]+T[O[j]], E[O[i]][O[j]])); } v = min(v, u); } printf("%d\n", v); } 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 | #include <cstdio> #include <algorithm> using namespace std; int main() { int t, n; scanf("%i ", &t); while (t--) { scanf("%i ", &n); int E[n][n], v = n; for (int i = 0; i<n; i++) { for (int j = 0; j<n; j++) E[i][j] = getchar()=='1'? 1: i==j? 0: n; scanf(" "); } for (int k = 0; k<n; k++) for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) E[i][j] = min(E[i][j], E[i][k]+E[k][j]); for (int x = 0; x<n; x++) for (int y = x+1; y<n; y++) { int T[n], O[n], u = 0; for (int k = 0; k<n; k++) T[k] = min(E[x][k], E[k][y]), O[k] = k; sort(O, O+n, [&](int a, int b){return T[a]>T[b];}); for (int i = 0; i<n; i++) for (int j = i+1; j<n; j++) { if (T[O[i]]+T[O[j]] <= u) break; u = max(u, min(T[O[i]]+T[O[j]], E[O[i]][O[j]])); } v = min(v, u); } printf("%d\n", v); } return 0; } |