Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Metodos
sorting using array and pointer
poker.hpp
Test 13(2020)
HeapSort
euler tour (by pure theory)
11
Decimal to Binary
XD
Problem: binary