Hola que tal. Espero no molestar a nadie, soy nuevo en programación y me gustaria saber si me pueden ayudar a resolver este problema en codigo c++.
Descripción
El último obstáculo de Gilgamesh para visitar a Utanapíshtim era cruzar las aguas de la muerte y el único que lo podía ayudar era el barquero Urshanabí. Éste le pidió a Gilgamesh que fuera al bosque a cortar R árboles para hacer los R remos que le faltaban. Como Gilgamesh estaba cansado, quería caminar lo menos posible para traer uno por uno los árboles necesarios. Escribe un programa que, dadas las coordenadas de N árboles, calcule la mínima distancia D que debe caminar Gilgamesh desde el origen. Gilgamesh sólo puede cargar un árbol a la vez.
Entrada
Dos enteros N y R, seguidos de N parejas de enteros, Xi,Yi que son las coordenadas (Xi,Yi) del árbol i.
Salida
El valor de D (redondeado al entero más cercano).
No entiendo bien lo que necesitas si no veo lo que llevas hecho pero, se me ocurre que puede ser de la siguiente manera el código:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
struct Point {
int x, y;
};
struct Edge {
int u, v;
double weight;
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};
vector<Point> trees;
vector<Edge> edges;
vector<int> parent;
int find(int x) {
if (parent
return x;
return parent
}
void unionSets(int x, int y) {
parent[find(x)] = find(y);
}
double calculateDistance(const Point& a, const Point& b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double minimumWalkingDistance(int N) {
sort(edges.begin(), edges.end());
double totalDistance = 0.0;
for (const Edge& edge : edges) {
if (find(edge.u) != find(edge.v)) {
unionSets(edge.u, edge.v);
totalDistance += edge.weight;
}
}
return totalDistance;
}
int main() {
int N, R;
cin >> N >> R;
trees.resize(N);
parent.resize(N);
for (int i = 0; i < N; ++i) {
cin >> trees
.x >> trees.y;
parent = i;
}
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
double distance = calculateDistance(trees, trees[j]);
edges.push_back({i, j, distance});
}
}
double minDistance = minimumWalkingDistance(N);
int roundedDistance = static_cast<int>(round(minDistance * R));
cout << roundedDistance << endl;
return 0;
}
Autor
En línea
