#include <iostream> #include <vector> #include <cstdlib> #include <algorithm> template <typename T> class BoundMatrix { std::vector<T> inner_; unsigned int dimx_, dimy_; public: BoundMatrix(unsigned int dimx, unsigned int dimy, T const& initialValue) : dimx_(dimx), dimy_(dimy) { inner_.resize(dimx_ * dimy_, initialValue); } T& operator()(unsigned int x, unsigned int y) { //if (x >= dimx_ || y >= dimy_) // throw std::out_of_range("matrix indices out of range"); // ouch return inner_[dimx_ * y + x]; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int ileTestow; std::cin >> ileTestow; for (int t = 0; t < ileTestow; ++t) { int n; std::cin >> n; std::vector<int> random_permutation; for (int i = 0; i < n; ++i) random_permutation.push_back(i); std::random_shuffle(random_permutation.begin(), random_permutation.end()); BoundMatrix<short> polaczenia = BoundMatrix<short>(n, n, n); for (int y = 0; y < n; ++y) { for (int x = 0; x < n; ++x) { char pol; std::cin >> pol; if (pol == '1') polaczenia(random_permutation[x], random_permutation[y]) = 1; } } for (int i = 0; i < n; ++i) { polaczenia(i, i) = 0; } BoundMatrix<short> odleglosci = polaczenia; BoundMatrix<short> newOdleglosci = odleglosci; for (int k = 0; k < n; ++k) { odleglosci = newOdleglosci; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) if (odleglosci(i, k) >= 0 && odleglosci(k,j) >= 0) newOdleglosci(i, j) = std::min(newOdleglosci(i, j), (short)(odleglosci(i,k) + odleglosci(k,j))); } } short minOdlegolsc = n; for (int telop1 = 0; telop1 < n; ++telop1) { for (int telop2 = telop1 + 1; telop2 < n; ++telop2) { short maxOdleglosc = 0; for (int a1 = 0; a1 < n; ++a1) { for (int a2 = a1 + 1; a2 < n; ++a2) { short odleglosc = std::min(newOdleglosci(a1, a2), (short)(newOdleglosci(a1, telop1) + newOdleglosci(a2, telop2))); odleglosc = std::min(odleglosc, (short)(newOdleglosci( a1, telop2) + newOdleglosci(a2, telop1))); maxOdleglosc = std::max(maxOdleglosc, odleglosc); if (maxOdleglosc >= minOdlegolsc) break; } if (maxOdleglosc >= minOdlegolsc) break; } minOdlegolsc = std::min(minOdlegolsc, maxOdleglosc); } } std::cout << minOdlegolsc << "\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 | #include <iostream> #include <vector> #include <cstdlib> #include <algorithm> template <typename T> class BoundMatrix { std::vector<T> inner_; unsigned int dimx_, dimy_; public: BoundMatrix(unsigned int dimx, unsigned int dimy, T const& initialValue) : dimx_(dimx), dimy_(dimy) { inner_.resize(dimx_ * dimy_, initialValue); } T& operator()(unsigned int x, unsigned int y) { //if (x >= dimx_ || y >= dimy_) // throw std::out_of_range("matrix indices out of range"); // ouch return inner_[dimx_ * y + x]; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int ileTestow; std::cin >> ileTestow; for (int t = 0; t < ileTestow; ++t) { int n; std::cin >> n; std::vector<int> random_permutation; for (int i = 0; i < n; ++i) random_permutation.push_back(i); std::random_shuffle(random_permutation.begin(), random_permutation.end()); BoundMatrix<short> polaczenia = BoundMatrix<short>(n, n, n); for (int y = 0; y < n; ++y) { for (int x = 0; x < n; ++x) { char pol; std::cin >> pol; if (pol == '1') polaczenia(random_permutation[x], random_permutation[y]) = 1; } } for (int i = 0; i < n; ++i) { polaczenia(i, i) = 0; } BoundMatrix<short> odleglosci = polaczenia; BoundMatrix<short> newOdleglosci = odleglosci; for (int k = 0; k < n; ++k) { odleglosci = newOdleglosci; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) if (odleglosci(i, k) >= 0 && odleglosci(k,j) >= 0) newOdleglosci(i, j) = std::min(newOdleglosci(i, j), (short)(odleglosci(i,k) + odleglosci(k,j))); } } short minOdlegolsc = n; for (int telop1 = 0; telop1 < n; ++telop1) { for (int telop2 = telop1 + 1; telop2 < n; ++telop2) { short maxOdleglosc = 0; for (int a1 = 0; a1 < n; ++a1) { for (int a2 = a1 + 1; a2 < n; ++a2) { short odleglosc = std::min(newOdleglosci(a1, a2), (short)(newOdleglosci(a1, telop1) + newOdleglosci(a2, telop2))); odleglosc = std::min(odleglosc, (short)(newOdleglosci( a1, telop2) + newOdleglosci(a2, telop1))); maxOdleglosc = std::max(maxOdleglosc, odleglosc); if (maxOdleglosc >= minOdlegolsc) break; } if (maxOdleglosc >= minOdlegolsc) break; } minOdlegolsc = std::min(minOdlegolsc, maxOdleglosc); } } std::cout << minOdlegolsc << "\n"; } return 0; } |