Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
MinCostKStops_BFS
/* 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; // Methods: DFS, BFS // BFS, define a node, including its name, cost, path struct Node{ string name; int cost; vector<string> path; Node(string nameV): name(nameV), cost(0){ path = vector<string>(1, nameV); // add the starting stop } }; class Solution { map<string, vector<pair<string,int>>> m; // the graph int minCost; vector<string> res; // result path public: vector<string> getPath(vector<vector<string>>& flights, string src, string dst, int K) { m.clear(); minCost = 1e9; // a large enough value for(auto f: flights){ m[f[0]].push_back({f[1], stoi(f[2])}); } queue<Node> q; // {airport, path } q.push(Node(src)); int steps = 0; while(q.size()){ steps++; if(steps > K+2) break; // finish searching on K+1 hop, note depends where to find the int n = q.size(); while(n--){ Node cur = q.front(); q.pop(); if(cur.name == dst){ if(cur.cost < minCost){ minCost = cur.cost; res = cur.path; } continue; } for(auto x: m[cur.name]){ string next = x.first; // next stop's name int cost = cur.cost + x.second; // cost from cur to next /*if(next == dst && cost < minCost){ // found a solution minCost = cost; res = cur.path; res.push_back(dst); }else */ if(cost < minCost){ // only push-back when, 剪枝 Node y(next); y.cost = cost; y.path = cur.path; y.path.push_back(next); q.push(y); } } } } if(minCost == 1e9) return {}; return res; } }; 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", 2); 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
Test 15(2020)
scemo le
shell sort
asa
cref
ww999
sdfg
带头结点的单链表
Matrix spiral print
Rotate90