地图路线算法

#include <iostream>
#include <vector>
#include <map>
#include <set>
const std::string townRelations = "洛阳-敦煌,28,129|嵩山,159,287|雁南,287,127\n"
                                  "苏州-镜湖,32,162|西湖,182,287|太湖,182,32\n"
                                  "// ...（省略了其他城镇关系）";

// 解析城镇之间的关系
std::map<std::string, std::vector<std::string>> parseTownRelations(const std::string& townRelations) {
    std::map<std::string, std::vector<std::string>> relations;
    std::istringstream ss(townRelations);
    std::string line;
    
    while (std::getline(ss, line)) {
        size_t pos = line.find('-');
        if (pos != std::string::npos) {
            std::string source = line.substr(0, pos);
            std::string targets = line.substr(pos + 1);
            std::istringstream targetsStream(targets);
            std::string branch;
            std::vector<std::string> branches;
            
            while (std::getline(targetsStream, branch, '|')) {
                size_t pos = branch.find(',');
                if (pos != std::string::npos) {
                    std::string target = branch.substr(0, pos);
                    branches.push_back(target);
                }
            }
            
            relations[source] = branches;
        } else {
            relations[line] = std::vector<std::string>();
        }
    }
    
    return relations;
}
// 查找城镇之间的路径
void findPath(const std::map<std::string, std::vector<std::string>>& graph, const std::string& start, const std::string& end,
              std::vector<std::string>& path, std::set<std::string>& visited) {
    path.push_back(start);
    visited.insert(start);
    
    if (start == end) {
        std::cout << "Path: ";
        for (const std::string& town : path) {
            std::cout << town << " -> ";
        }
        std::cout << std::endl;
        return;
    }
    const auto& neighbors = graph.find(start);
    if (neighbors != graph.end()) {
        for (const std::string& neighbor : neighbors->second) {
            if (visited.find(neighbor) == visited.end()) {
                findPath(graph, neighbor, end, path, visited);
            }
        }
    }
}
int main() {
    // 解析城镇关系
    std::map<std::string, std::vector<std::string>> townGraph = parseTownRelations(townRelations);

    // 查找从 '洛阳' 到 '无量山' 的路径
    std::vector<std::string> path;
    std::set<std::string> visited;
    findPath(townGraph, "洛阳", "无量山", path, visited);

    return 0;
}