Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <string>
- #include <unordered_map>
- #include <queue>
- class Solution {
- public:
- std::vector<std::string> findItinerary(std::vector<std::vector<std::string>>& tickets) {
- std::unordered_map<std::string, std::priority_queue<std::string, std::vector<std::string>, std::greater<std::string>>> graph;
- std::vector<std::string> itinerary;
- for (const auto& ticket : tickets) {
- graph[ticket[0]].push(ticket[1]);
- }
- visitAirport("JFK", graph, itinerary);
- std::reverse(itinerary.begin(), itinerary.end());
- return itinerary;
- }
- void visitAirport(const std::string& airport, std::unordered_map<std::string, std::priority_queue<std::string, std::vector<std::string>, std::greater<std::string>>>& graph, std::vector<std::string>& itinerary) {
- while (!graph[airport].empty()) {
- std::string nextAirport = graph[airport].top();
- graph[airport].pop();
- visitAirport(nextAirport, graph, itinerary);
- }
- itinerary.push_back(airport);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement