#include <bits/stdc++.h> using namespace std; typedef long long int ll; constexpr int N = 400; vector<int> graf[N+9]; int dst[N+9][N+9]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t,n; string a; cin >> t; while(t--){ cin >> n; for (int x=1;x<=n;x++){ cin >> a; for (int y=0;y<n;y++){ if (a[y]=='1')graf[x].push_back(y+1); } } for (int pocz=1;pocz<=n;pocz++){ for (int x=1;x<=n;x++)dst[pocz][x]=1e9; dst[pocz][pocz]=0; vector<int> kolej; kolej.push_back(pocz); for (int x=0;x<kolej.size();x++){ int v=kolej[x]; for (int y:graf[v]){ if (dst[pocz][y]==1e9){ dst[pocz][y]=dst[pocz][v]+1; kolej.push_back(y); } } } } int best=1e9; for (int x1=1;x1<=n;x1++){ for (int x2=1;x2<=n;x2++){ int temp=0; for (int x=1;x<=n;x++){ for (int y=1;y<=n;y++){ temp=max(temp, min(dst[x][y],min(dst[x][x1]+dst[x2][y]+1,dst[x][x2]+dst[x1][y]+1))); } } best=min(best,temp); } } cout << best << '\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 | #include <bits/stdc++.h> using namespace std; typedef long long int ll; constexpr int N = 400; vector<int> graf[N+9]; int dst[N+9][N+9]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t,n; string a; cin >> t; while(t--){ cin >> n; for (int x=1;x<=n;x++){ cin >> a; for (int y=0;y<n;y++){ if (a[y]=='1')graf[x].push_back(y+1); } } for (int pocz=1;pocz<=n;pocz++){ for (int x=1;x<=n;x++)dst[pocz][x]=1e9; dst[pocz][pocz]=0; vector<int> kolej; kolej.push_back(pocz); for (int x=0;x<kolej.size();x++){ int v=kolej[x]; for (int y:graf[v]){ if (dst[pocz][y]==1e9){ dst[pocz][y]=dst[pocz][v]+1; kolej.push_back(y); } } } } int best=1e9; for (int x1=1;x1<=n;x1++){ for (int x2=1;x2<=n;x2++){ int temp=0; for (int x=1;x<=n;x++){ for (int y=1;y<=n;y++){ temp=max(temp, min(dst[x][y],min(dst[x][x1]+dst[x2][y]+1,dst[x][x2]+dst[x1][y]+1))); } } best=min(best,temp); } } cout << best << '\n'; } } |