MinCostKStops_DFS, C++ (gcc)

MinCostKStops_DFS

/* 25 Minimum Cost with At Most K Stops
-- Similar：leetcode 787
Given a flight itinerary consisting of starting city, destination city, and ticket price (2d list) 
- find the optimal price flight path to get from start to destination. (A variation of Dynamic Programming Shortest Path)
*/
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

class Solution{
    map<string, vector<pair<string, int>>> m; 
    int minCost; 
    vector<string> minPath; 
public: 
    vector<string> getPath(vector<vector<string>>& flights, string src, string dst, int K) { // K transfer 
        // change input to a graph 
        m.clear(); 
        for(auto f: flights){
            string A = f[0], B = f[1]; 
            int cost = stoi(f[2]); 
            m[A].push_back({B, cost}); 
        }
        
        minCost = 1e9; // large enough, but not 
        int cost = 0; 
        vector<string> path; // interim path;
        path.push_back(src);
        DFS(src, dst, K+1, cost, path); 
        if(minCost == 1e9) return {}; 
        return minPath; 
    }
    void DFS(string src, string dst, int sections, int cost, vector<string> path){
        if(cost > minCost) return; 
        if(sections < 0) return; 
        if(src == dst) { // also sections >=0
            if(cost < minCost){
                minCost = cost;
                minPath = path;
                return; 
            }
        }
        for(auto x: m[src]){
            string nextStop = x.first;
            path.push_back(nextStop); 
            DFS(nextStop, dst, sections-1, cost + x.second, path);
            path.pop_back();
        }
    }
};

int main() {
    vector<vector<string>> flights = { 
        {"A","B", "100"},   
        {"B","C", "100"},   
        {"A","C", "500"}, {"A","D", "5"}, {"D","E", "5"}, {"E","C", "5"} };
    Solution s; 
    vector<string> res = s.getPath( flights, "A", "C", 0);
    cout << res.size() << endl;
    for(int i=0; i<res.size(); i++) {
        cout << res[i];
        if( i!=res.size()-1) cout << "->"; 
    }
    cout << endl;
            
    return 0; 
}


run \| edit \| history \| help	0

Please log in to post a comment.