A*

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <cmath>
#include <climits>

using namespace std;

// Структура для хранения информации о вершине
struct Vertex {
    double g = numeric_limits<double>::max(); // Стоимость пути от начальной вершины до данной
    double h; // Эвристическая оценка стоимости пути от данной вершины до конечной
    double f; // Общая стоимость пути (g + h)
    char parent; // Родительская вершина в пути
};

// Структура для сравнения вершин в очереди
struct Compare {
    bool operator()(const pair<char, Vertex>& a, const pair<char, Vertex>& b) {
        return a.second.f > b.second.f;
    }
};

// Функция для вычисления эвристической оценки
double heuristic(char a, char b) {
    return abs(a - b);
}

string aStar(map<char, vector<pair<char, double>>>& graph, char start, char goal) {
    map<char, Vertex> vertices;
    priority_queue<pair<char, Vertex>, vector<pair<char, Vertex>>, Compare> pq;

    // Инициализация начальной вершины
    vertices[start].g = 0;
    vertices[start].h = heuristic(start, goal);
    vertices[start].f = vertices[start].g + vertices[start].h;
    vertices[start].parent = ' ';
    pq.push({ start, vertices[start] });

    while (!pq.empty()) {
        char current = pq.top().first;
        pq.pop();

        if (current == goal) {
            string path;
            while (current != ' ') {
                path = current + path;
                current = vertices[current].parent;
            }
            return path;
        }

        for (auto& neighbor : graph[current]) {
            char next = neighbor.first;
            double tentative_g = vertices[current].g + neighbor.second;

            //cout << next << ' ' << tentative_g << ' ' << vertices[next].g << '\n';

            if (tentative_g < vertices[next].g) {
                vertices[next].g = tentative_g;
                vertices[next].h = heuristic(next, goal);
                vertices[next].f = vertices[next].g + vertices[next].h;
                vertices[next].parent = current;
                pq.push({ next, vertices[next] });
            }
        }

        //cout << current << '\n';
    }

    return "No path found";
}

int main() {
    map<char, vector<pair<char, double>>> graph;
    char start, goal;
    cin >> start >> goal;

    char from, to;
    double weight;
    while (cin >> from >> to >> weight) {
        graph[from].insert(graph[from].end(), {make_pair(to, weight)});
    }

    /*for (const auto& vert : graph) {
        std::cout << "vert = " << vert.first << '\n';
        for (const auto& pair : vert.second) {
            std::cout << " end vert = " << pair.first << " weight = " << pair.second;
        }
        std::cout << "\n";
    }*/

    string path = aStar(graph, start, goal);
    cout << path << endl;

    return 0;
}