Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
10 wizards
/*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 Wizard{ int miniCost; public: Wizard(){ } int findCost(vector<vector<int>>& costs, int src, int dst){ miniCost = 1<<30; int cost = 0; set<int> visited;// DFS(costs, src, dst, cost, visited); if(miniCost == 1<<30) return -1; return miniCost; } private: void DFS(vector<vector<int>>& costs, int src, int dst, int cost, set<int>& visited){ if(cost > miniCost) return; // too expensive if(src == dst){ // find a possible solution if(cost < miniCost) miniCost = min(cost, miniCost); return; // always return, } visited.insert(src); // visit node for(auto next: costs[src]){ // visit node's neighbors if(visited.count(next)) continue; DFS(costs, next, dst, cost + (next-src)*(next-src), visited); } } }; int main(){ vector<vector<int>> costs(10); costs[0] = {1,4,5}; costs[4] = {9}; Wizard w; int cost = w.findCost(costs, 0, 4);// cout << "cost should equal (41) = " << cost << endl; return 0; }
run
|
edit
|
history
|
help
0
max_recursion
ttt
sheetal
My love
Conjuntos - Contar caracteres únicos
C5P20
LRU cache
Hello
345325
4149 coj TL