10 wizards-DFS_vector, C++ (gcc)

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