#include <iostream> #include <vector> #include <unordered_map> using namespace std; int get_min_dist_index(vector<int> dists, vector<bool> visited) { int min_index, min = 400; for (int v = 0; v < visited.size(); v++) { if (dists[v] <= min && visited[v] == false) { min = dists[v]; min_index = v; } } return min_index; } int get_max(vector<int> v) { int max = -1; for (int e : v) { if (e > max) max = e; } return max; } int get_min_fuel_size(vector<string> graph, int n) { int min_fuel_size = 400; for (int src = 0; src < n; src++) { vector<int> dists(n); vector<bool> visited(n); for (int i = 0; i < n; i++) { dists[i] = 400; visited[i] = false; } dists[src] = 0; for (int c = 0; c < n - 1; c++) { int u = get_min_dist_index(dists, visited); visited[u] = true; for (int v = 0; v < n; v++) { if (dists[u] != 400 && !visited[v] && graph[u][v] != '0') { if ((graph[u][v] == '1' || graph[u][v] == '3') && dists[u] + 1 < dists[v]) { dists[v] = dists[u] + 1; } else if (graph[u][v] == '2' && dists[u] < dists[v]) { dists[v] = dists[u]; } } } } // printing solution // for (int k = 0; k < n; k++) { // cout << dists[k] << "\n"; // } // cout << "\n"; if (min_fuel_size > get_max(dists)) min_fuel_size = get_max(dists); } return min_fuel_size; } int main() { int t, n, min_fuel_size; cin >> t; while (t--) { cin >> n; vector<string> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } min_fuel_size = 400; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (v[i][j] == '1') { v[i][j] = '2'; v[j][i] = '2'; int current_min_fuel_size = get_min_fuel_size(v, n); if (current_min_fuel_size < min_fuel_size) min_fuel_size = current_min_fuel_size; v[i][j] = '3'; v[j][i] = '3'; } } } cout << min_fuel_size << "\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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <iostream> #include <vector> #include <unordered_map> using namespace std; int get_min_dist_index(vector<int> dists, vector<bool> visited) { int min_index, min = 400; for (int v = 0; v < visited.size(); v++) { if (dists[v] <= min && visited[v] == false) { min = dists[v]; min_index = v; } } return min_index; } int get_max(vector<int> v) { int max = -1; for (int e : v) { if (e > max) max = e; } return max; } int get_min_fuel_size(vector<string> graph, int n) { int min_fuel_size = 400; for (int src = 0; src < n; src++) { vector<int> dists(n); vector<bool> visited(n); for (int i = 0; i < n; i++) { dists[i] = 400; visited[i] = false; } dists[src] = 0; for (int c = 0; c < n - 1; c++) { int u = get_min_dist_index(dists, visited); visited[u] = true; for (int v = 0; v < n; v++) { if (dists[u] != 400 && !visited[v] && graph[u][v] != '0') { if ((graph[u][v] == '1' || graph[u][v] == '3') && dists[u] + 1 < dists[v]) { dists[v] = dists[u] + 1; } else if (graph[u][v] == '2' && dists[u] < dists[v]) { dists[v] = dists[u]; } } } } // printing solution // for (int k = 0; k < n; k++) { // cout << dists[k] << "\n"; // } // cout << "\n"; if (min_fuel_size > get_max(dists)) min_fuel_size = get_max(dists); } return min_fuel_size; } int main() { int t, n, min_fuel_size; cin >> t; while (t--) { cin >> n; vector<string> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } min_fuel_size = 400; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (v[i][j] == '1') { v[i][j] = '2'; v[j][i] = '2'; int current_min_fuel_size = get_min_fuel_size(v, n); if (current_min_fuel_size < min_fuel_size) min_fuel_size = current_min_fuel_size; v[i][j] = '3'; v[j][i] = '3'; } } } cout << min_fuel_size << "\n"; } } |