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>
- // граф - ориентированный
- struct Vertex {
- bool visited = false;
- int neighbors_num;
- };
- std::vector<char> greedy_alg(std::map<char, std::vector<std::pair<char, double>>>& graph, char start, char end) {
- std::vector<char> path = {start};
- std::map<char, Vertex> vertices;
- double inf = std::numeric_limits<double>::max();
- double minWeight = inf;
- char current = start;
- vertices[start].visited = true;
- vertices[start].neighbors_num = graph[current].size();
- while (current != end) {
- if (!vertices[current].visited) {
- vertices[current].neighbors_num = graph[current].size();
- vertices[current].visited = true;
- }
- if (vertices[current].neighbors_num == 0) {
- path.pop_back();
- current = path[path.size() - 1];
- }
- char next;
- for (const auto& vert : graph[current]) {
- if (graph[vert.first].size() == 0 && vert.first != end) {
- vertices[current].neighbors_num--;
- continue;
- }
- else if (graph[vert.first].size() == 0 && vert.first == end) {
- path.push_back(end);
- return path;
- }
- if (vert.second < minWeight && graph[vert.first].size() > 0) {
- minWeight = vert.second;
- next = vert.first;
- }
- }
- path.push_back(next);
- minWeight = inf;
- current = next;
- }
- return path;
- }
- int main() {
- std::map<char, std::vector<std::pair<char, double>>> graph;
- char start, end;
- std::cin >> start >> end;
- char from, to;
- double weight;
- while (std::cin >> from >> to >> weight) {
- graph[from].insert(graph[from].end(), { std::make_pair(to, weight) });
- }
- std::vector<char> res = greedy_alg(graph, start, end);
- for (const auto& it : res) {
- std::cout << it;
- }
- std::cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement