10 Wizards-DP, C++ (gcc)

10 Wizards-DP

/*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])
*/
// DP or Bellman-ford 
#include <iostream>
#include <vector>
using namespace std;

struct Node { // it is easy to define a node to make thing clear 
  int money;
  vector<int> path;
  Node():money(1<<30) {
    path = vector<int>(0);
  }
};

class Wizard3 {
public: 
  Node findBest(vector<vector<int>>& wizards, int src, int dst){
    int n = wizards.size();
    vector<Node> costs(n, Node()); 
    costs[src].money = 0;
    costs[src].path.push_back(src);
    
    for(int k=0; k < n; k++){
      auto orig(costs);  // make a copy of the orig cost 
      for(int i=0; i<n; i++){   //ith
        for(int j=0; j<(int)wizards[i].size(); j++){
          int t = wizards[i][j]; // t-th
          
          int newCost = orig[i].money + (t-i)*(t-i); 
          if(newCost < costs[t].money){
            costs[t] = orig[i]; // i->t
            costs[t].money = newCost; 
            costs[t].path.push_back(t);  
          }
            
        }
      }
    }
    if(costs[dst].money == 1<<30) return Node();
    return costs[dst]; 
  }  
};

void print(Node& n){
  cout << "Cost = " << n.money << endl;
  for(auto x: n.path) 
    cout << x << " "; 
  cout << endl;
}

int main() {
  vector<vector<int>> wizards = {{1,4,5}, {}, {},{}, {8,9},{},{},{},{9},{}};
  Wizard3 s; 
  Node res = s.findBest(wizards, 0, 9);
  print(res);
  
  return 0;
}


run \| edit \| history \| help	0