#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>

struct Location {
	double x, y;
	double operator[](const Location &other) const {
		return sqrt((this->x - other.x) * (this->x - other.x) + (this->y - other.y) * (this->y - other.y));
	}
	Location operator=(const Location &other) {
		this->x = other.x;
		this->y = other.y;
		return *this;
	}
	friend std::istream& operator>>(std::istream &is, Location &location) {
		is >> location.x >> location.y;
		return is;
	}
	Location(const double &c_x = 0, const double &c_y = 0) {
		x = c_x;
		y = c_y;
	}
};

struct Node {
	int id;
	Location location;
	std::vector<int> id_of_neighbours;
	std::vector<double> cost_of_neighbours;
	Node operator=(const Node &other) {
		this->id = other.id;
		this->location = other.location;
		this->id_of_neighbours = other.id_of_neighbours;
		this->cost_of_neighbours = other.cost_of_neighbours;
		return *this;
	}
	friend std::istream& operator>>(std::istream &is, Node &node) {
		is >> node.id >> node.location;
		int numberOfNeighbours;
		is >> numberOfNeighbours;
		for (int i = 0; i < numberOfNeighbours; i++) {
			int buffer;
			is >> buffer;
			node.id_of_neighbours.push_back(buffer);
		}
		for (int i = 0; i < numberOfNeighbours; i++) {
			double buffer;
			is >> buffer;
			node.cost_of_neighbours.push_back(buffer);
		}
		return is;
	}
	Node(const int &c_id = 0, const Location &c_location = { 0, 0 }) {
		id = c_id;
		location = c_location;
	}
};

struct Pair {
	int id;
	double cost;
	bool operator<(const Pair &other) const {
		return this->cost < other.cost;
	}
	bool operator>(const Pair &other) const {
		return this->cost > other.cost;
	}
	Pair operator=(const Pair &other) {
		this->id = other.id;
		this->cost = other.cost;
		return *this;
	}
	Pair(const int &c_id, const double &c_cost) {
		id = c_id;
		cost = c_cost;
	}
};

template<typename T>
class MinHeap {
private:
	std::vector<T> elements;
	void siftUp(const int &currentPosition) {
		if (currentPosition != 0) {
			int father = (currentPosition - 1) / 2;
			if (elements[father] > elements[currentPosition]) {
				std::swap(elements[father], elements[currentPosition]);
				this->siftUp(father);
			}
		}
	}
	void siftDown(int &currentPosition) {
		int leftSon = currentPosition * 2 + 1, rightSon = currentPosition * 2 + 2;
		while ((elements[currentPosition] > elements[leftSon]) || (elements[currentPosition] > elements[rightSon])) {
			if (elements[leftSon] < elements[rightSon]) {
				std::swap(elements[leftSon], elements[currentPosition]);
				currentPosition = leftSon;
				leftSon = currentPosition * 2 + 1;
				rightSon = currentPosition * 2 + 2;
			}
			else {
				std::swap(elements[rightSon], elements[currentPosition]);
				currentPosition = rightSon;
				leftSon = currentPosition * 2 + 1;
				rightSon = currentPosition * 2 + 2;
			}
		}
	}
public:
	void insert(const T &toInsert) {
		elements.push_back(toInsert);
		this->siftUp(elements.size() - 1);
	}
	T extractMax() {
		T toReturn = elements[0];
		std::swap(elements[0], elements[elements.size() - 1]);
		elements.erase(elements.begin() + elements.size() - 1);
		this->siftDown();
		return toReturn;
	}
	T maxElement() const {
		return elements[0];
	}
	bool empty() const {
		return elements.empty();
	}
	void constructHeap(const std::vector<T> &buildFrom) {
		for (auto val : buildFrom) {
			this->insert(val);
		}
	}
	void printVector() const {
		for (auto val : elements) {
			std::cout << val << " ";
		}
	}
};

double heu(const Node &first, const Node &second, const double minCost) {
	return first.location[second.location] * minCost;
}

void readGraph(std::vector<Node> &graph) {
	std::ifstream fin("graph.in");
	int numberOfNodes;
	fin >> numberOfNodes;
	for (int i = 0; i < numberOfNodes; i++){
		Node toAdd;
		fin >> toAdd;
		graph.push_back(toAdd);
	}
}

double getMinCost(const std::vector<Node> &graph) {
	double minimum = INT32_MAX;
	for (auto node : graph) {
		for (auto val : node.cost_of_neighbours) {
			minimum = std::min(minimum, val);
		}
	}
	return minimum;
}

bool AStar(const std::vector<Node> graph, const int &start, const int &finish) {
	double minCost = getMinCost(graph);
	bool *visited = new bool[graph.size()];
	for (int i = 0; i < graph.size(); ++i)
		visited[i] = false;
	visited[start] = true;
	int *prev = new int[graph.size()];
	for (int i = 0; i < graph.size(); ++i)
		prev[i] = i;
	double *costUpUntil = new double[graph.size()];
	for (int i = 0; i < graph.size(); ++i)
		costUpUntil[i] = INT32_MAX;
	costUpUntil[start] = 0;
	Pair auxilliary(start, heu(graph[start], graph[finish], minCost));
	MinHeap<Pair> frontier;
	for (frontier.insert(auxilliary); frontier.empty() == false; ) {

	}
}

int main() {
	std::vector<Node> graph;
	return 0;
}