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>
- //граф - ориентированный
- using Graph = std::map<std::pair<char, char>, double>;
- using Neighbors = std::map<char, std::vector<char>>;
- Graph edges;
- Neighbors vertices;
- std::vector<char> greedy_alg(char start, char end) {
- std::vector<char> previous;
- std::vector<char> path;
- previous.push_back(start);
- char current = start;
- double inf = std::numeric_limits<double>::infinity();
- double minWeight = inf;
- while(current != end){
- if (vertices[current].empty()) {
- previous.pop_back();
- char tmp = current;
- current = previous[previous.size() - 1];
- vertices[current].erase(std::remove(vertices[current].begin(), vertices[current].end(), tmp), vertices[current].end());
- continue;
- }
- char tmp_v;
- for (const auto& vert : vertices[current]) {
- if (edges[std::make_pair(current, vert)] < minWeight) {
- minWeight = edges[std::make_pair(current, vert)];
- tmp_v = vert;
- }
- }
- previous.push_back(tmp_v);
- minWeight = inf;
- current = previous[previous.size() - 1];
- path.push_back(current);
- }
- return previous;
- }
- int main() {
- char start, end;
- std::cin >> start >> end;
- char v_st, v_end;
- double weight;
- while (std::cin >> v_st >> v_end >> weight) {
- edges[std::make_pair(v_st, v_end)] = weight;
- vertices[v_st].insert(vertices[v_st].end(), { v_end });
- }
- std::vector<char> res = greedy_alg(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