// Application de l'arbre de recouvrement minimal (Minimum Spanning Tree) // Algorithme de Prim // https://prologin.org/train/2016/qualification/apres_le_deluge #include #include #include #include #include using namespace std; struct point_t { int x, y; point_t() : x(0), y(0) { } point_t(int _x, int _y) : x(_x), y(_y) { } }; // Distance euclidienne entre deux points double distance(const point_t &p, const point_t &q) { return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y)); } // distance() /**********************/ /* Algorithme de PRIM */ /**********************/ // https://www.codingninjas.com/codestudio/library/minimum-cost-to-connect-all-cities int findMinNode(const vector &weight, const vector &visited, int n) { int minIndex = -1; for(int i = 0; i < n; i++) if(!visited[i] && (minIndex == -1 || weight[i] < weight[minIndex])) minIndex = i; return minIndex; } // findMinNode() // Algorithme de Prim double prim(vector> &iles) { int n = iles.size(); vector weight(n, 50000001.0); vector visited(n, false); vector parent(n, -1); weight[0] = 0.0; for(int i = 1; i <= n - 1; i++) { int minNode = findMinNode(weight, visited, n); visited[minNode] = true; for(int j = 0; j < n; j++) { if(iles[minNode][j] > 0 && !visited[j]) { if(iles[minNode][j] < weight[j]) { weight[j] = iles[minNode][j]; parent[j] = minNode; } } } } double ans = 0.0; for(int i = 1; i < n; i++) ans += weight[i]; return ans; } // prim() int main() { // Lecture des données int n = 0; cin >> n; auto iles = vector>(n, vector(2, 0)); for(int i = 0; i < n; i++) cin >> iles[i][0] >> iles[i][1]; // Graphe représenté par une matrice d'adjacences auto graphe = vector>(n, vector(n, 0.0)); for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) if(i != j) { point_t p(iles[i][0], iles[i][1]); point_t q(iles[j][0], iles[j][1]); graphe[i][j] = graphe[j][i] = distance(p, q); } // Résolution double minCost = prim(graphe); cout << (int)floor(minCost) << '\n'; return 0; } // main()