#include <algorithm> #include <bits/stdc++.h> using namespace std; // Funkcja BFS zwraca w wektorze dist odległości od start do wszystkich wierzchołków void bfs_dist(int start, int n, const vector<vector<bool>> &adj, vector<int> &dist) { const int INF = 1e9; for(int i = 0; i < n; i++){ dist[i] = INF; } dist[start] = 0; queue<int> q; q.push(start); while(!q.empty()){ int u = q.front(); q.pop(); int dnow = dist[u]; for(int v = 0; v < n; v++){ if(adj[u][v] && dist[v] == INF){ dist[v] = dnow + 1; q.push(v); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; // liczba testów while(t--){ int n; cin >> n; // Wczytujemy macierz sąsiedztwa vector<vector<bool>> adj(n, vector<bool>(n, false)); for(int i = 0; i < n; i++){ // Wczytujemy wiersz jako ciąg znaków '0'/'1' string row; cin >> row; for(int j = 0; j < n; j++){ if(row[j] == '1'){ adj[i][j] = true; } } } // Obliczamy odległości: dist[u][v] = minimalna liczba krawędzi z u do v static vector<int> tmpDist(400); vector<vector<int>> dist(n, vector<int>(n)); for(int u = 0; u < n; u++){ bfs_dist(u, n, adj, tmpDist); for(int v = 0; v < n; v++){ dist[u][v] = tmpDist[v]; } } // Obliczamy bieżącą średnicę (max dist[u][v]) int diameter = 0; for(int u = 0; u < n; u++){ for(int v = 0; v < n; v++){ diameter = max(diameter, dist[u][v]); } } // Jeśli średnica ≤ 1, teleport nie pomaga if(diameter <= 1){ cout << diameter << "\n"; continue; } // Tworzymy listę par (x,y), które są warte sprawdzenia // (np. w odległości >= diameter - 1). W praktyce można wężej wybierać vector<pair<int,int>> candidates; candidates.reserve(n*n); for(int x = 0; x < n; x++){ for(int y = x+1; y < n; y++){ if(dist[x][y] >= diameter - 1){ candidates.push_back({x, y}); } } } int best = diameter; // nie gorszy niż stara średnica // Sprawdzamy każdą parę (x,y) i wyliczamy "nową średnicę" for(auto &pr : candidates){ int x = pr.first, y = pr.second; int new_diam = 0; // nowa_odl(a,b) = min(dist[a][b], dist[a][x] + dist[y][b], dist[a][y] + dist[x][b]) for(int a = 0; a < n; a++){ for(int b = a+1; b < n; b++){ int candDist = dist[a][b]; int c2 = dist[a][x] + dist[y][b]; if(c2 < candDist) candDist = c2; int c3 = dist[a][y] + dist[x][b]; if(c3 < candDist) candDist = c3; if(candDist > new_diam){ new_diam = candDist; // Jeśli i tak przekroczyliśmy current best, można przerwać if(new_diam >= best) break; } } if(new_diam >= best) break; } if(new_diam < best){ best = new_diam; } } cout << best << "\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 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 | #include <algorithm> #include <bits/stdc++.h> using namespace std; // Funkcja BFS zwraca w wektorze dist odległości od start do wszystkich wierzchołków void bfs_dist(int start, int n, const vector<vector<bool>> &adj, vector<int> &dist) { const int INF = 1e9; for(int i = 0; i < n; i++){ dist[i] = INF; } dist[start] = 0; queue<int> q; q.push(start); while(!q.empty()){ int u = q.front(); q.pop(); int dnow = dist[u]; for(int v = 0; v < n; v++){ if(adj[u][v] && dist[v] == INF){ dist[v] = dnow + 1; q.push(v); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; // liczba testów while(t--){ int n; cin >> n; // Wczytujemy macierz sąsiedztwa vector<vector<bool>> adj(n, vector<bool>(n, false)); for(int i = 0; i < n; i++){ // Wczytujemy wiersz jako ciąg znaków '0'/'1' string row; cin >> row; for(int j = 0; j < n; j++){ if(row[j] == '1'){ adj[i][j] = true; } } } // Obliczamy odległości: dist[u][v] = minimalna liczba krawędzi z u do v static vector<int> tmpDist(400); vector<vector<int>> dist(n, vector<int>(n)); for(int u = 0; u < n; u++){ bfs_dist(u, n, adj, tmpDist); for(int v = 0; v < n; v++){ dist[u][v] = tmpDist[v]; } } // Obliczamy bieżącą średnicę (max dist[u][v]) int diameter = 0; for(int u = 0; u < n; u++){ for(int v = 0; v < n; v++){ diameter = max(diameter, dist[u][v]); } } // Jeśli średnica ≤ 1, teleport nie pomaga if(diameter <= 1){ cout << diameter << "\n"; continue; } // Tworzymy listę par (x,y), które są warte sprawdzenia // (np. w odległości >= diameter - 1). W praktyce można wężej wybierać vector<pair<int,int>> candidates; candidates.reserve(n*n); for(int x = 0; x < n; x++){ for(int y = x+1; y < n; y++){ if(dist[x][y] >= diameter - 1){ candidates.push_back({x, y}); } } } int best = diameter; // nie gorszy niż stara średnica // Sprawdzamy każdą parę (x,y) i wyliczamy "nową średnicę" for(auto &pr : candidates){ int x = pr.first, y = pr.second; int new_diam = 0; // nowa_odl(a,b) = min(dist[a][b], dist[a][x] + dist[y][b], dist[a][y] + dist[x][b]) for(int a = 0; a < n; a++){ for(int b = a+1; b < n; b++){ int candDist = dist[a][b]; int c2 = dist[a][x] + dist[y][b]; if(c2 < candDist) candDist = c2; int c3 = dist[a][y] + dist[x][b]; if(c3 < candDist) candDist = c3; if(candDist > new_diam){ new_diam = candDist; // Jeśli i tak przekroczyliśmy current best, można przerwać if(new_diam >= best) break; } } if(new_diam >= best) break; } if(new_diam < best){ best = new_diam; } } cout << best << "\n"; } return 0; } |