Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <utility>
- #include <string>
- #include <limits>
- #include <sstream>
- template<typename T>
- std::vector<T> greedy_alg(std::map<T, std::vector<std::pair<T, double>>>& graph, T start, T end) {
- std::vector<T> path = { start };
- std::map<T, std::pair<bool, int>> vertices; // словарь, хранящий информацию о том, посещалась ли это вершина и в какое количество вершин из нее можно перейти
- double inf = std::numeric_limits<double>::max();
- double minWeight = inf;
- int current = start;
- vertices[start] = { true, graph[current].size() };
- while (current != end) {
- auto& vertex = vertices[current];
- if (!vertex.first) { // проверяем посещали ли до этого текущую вершину
- vertex.second = graph[current].size();
- vertex.first = true;
- }
- if (vertex.second == 0) { // если у вершины нет соседей из которых можно попасть в конец, возвращаемся к предыдущей вершине
- path.pop_back();
- if (!path.empty()) {
- current = path.back();
- }
- continue;
- }
- int tmp;
- char next;
- std::string str = "Possible paths:";
- std::string d = "Deadends:";
- std::stringstream out;
- std::stringstream ssd;
- std::cout << "Current vertice: " << current << '\n';
- for (const auto& vert : graph[current]) {
- tmp = !vertices[vert.first].first ? graph[vert.first].size() : vertices[vert.first].second; // количество соседей из которых потенциально можно дойти до конца
- if (vert.second < minWeight && tmp > 0) { // отбираем нужную вершину
- minWeight = vert.second;
- next = vert.first;
- }
- if (vert.second < minWeight && tmp == 0 && vert.first != end) { // сосед оказался тупиком
- vertex.second--;
- ssd << ' ' << vert.first;
- continue;
- }
- if (vert.second < minWeight && vert.first == end) { // дошли до конца
- path.push_back(end);
- return path;
- }
- out << " | " << current << "-" << vert.first << ": " << vert.second << "(weight) | ";
- }
- str = (str + out.str()).length() > str.length() ? str + out.str() : str + " None";
- std::cout << str << '\n';
- d = (d + ssd.str()).length() > d.length() ? d + ssd.str() + '\n' : "";
- std::cout << d;
- path.push_back(next);
- minWeight = inf;
- current = next;
- }
- return path;
- }
- int main() {
- std::map<int, std::vector<std::pair<int, double>>> graph;
- int start, end;
- std::cin >> start >> end;
- char from, to;
- double weight;
- while (std::cin >> from >> to >> weight) {
- graph[from].emplace_back(to, weight);
- }
- std::vector<int> res = greedy_alg(graph, start, end);
- std::cout << "Path: ";
- for (const auto& it : res) {
- std::cout << it;
- }
- std::cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement