Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
10 wizards-DFS_vector
/*30 10 Wizards There are 10 wizards, 0‑9, you are given a list that each entry is a list of wizards known by wizard. Define the cost between wizards and wizard as square of different of i and j. To find the min cost between 0 and 9. For example: wizard[0] list: 1, 4, 5 wizard[4] list: 9 wizard 0 to 9 min distance is (0‑4)^2+(4‑9)^2=41 (wizard[0]‑>wizard[4]‑>wizard[9]) */ #include <iostream> #include <vector> #include <set> using namespace std; // DFS to get the minimum cost with the path vector return .... class Wizard2{ int miniCost; vector<int> miniPath; public: vector<int> findCost(vector<vector<int>>& costs, int src, int dst){ miniCost = 1<<30; int cost = 0; vector<int> path; set<int> visited; DFS(costs, src, dst, cost, path, visited); if(miniCost==1<<30) return {}; return miniPath; } private: void DFS(vector<vector<int>>& costs, int src, int dst, int cost, vector<int>& path, set<int>& visited){ if(cost > miniCost) return; // too expensive if(src == dst){ // find a possible solution if(cost < miniCost) { miniCost = cost; miniPath = path; miniPath.push_back(src); // add the last node } return; } visited.insert(src); for(auto next: costs[src]){ if(visited.count(next)) continue; path.push_back(src); // <- push-in src here DFS(costs, next, dst, cost + (next-src)*(next-src), path, visited); path.pop_back(); // post actions } } public: void print(){ for(auto x: miniPath) cout << " " << x; cout << endl; cout << "mini-cost = " << miniCost << endl; } }; int main(){ vector<vector<int>> costs(10); costs[0] = {1,4,5}; costs[4] = {9}; Wizard2 w; vector<int> res = w.findCost(costs, 0, 9); // w.print(); return 0; }
run
|
edit
|
history
|
help
0
c++
პირამიდის ფართობი~ფინალური
Depth of Bin tree
new
p30
multimap
11
Do While Meteoro Agustin
CurDayMessage
A+B ორობით სისტემაში