Guest User

minimal path sum from top-left to bottom-right

a guest
Sep 13th, 2014
392
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <queue>
  2. #include <limits>
  3.  
  4. const int rows=80;
  5. const int cols=80;
  6. int input[rows*cols]; // input matrix goes here
  7. int mat[rows*cols]; // temporary results are kept here
  8. // initialize mat[] as:
  9. // for(int i=0;i<rows*cols;i++)
  10. //     mat[i] = std::numeric_limits<int>::max();
  11.  
  12. // std::priority_queue, by default, sorts elements in descending order
  13. // we need them in ascending order
  14. class greater
  15. {
  16. public:
  17.     bool operator()(const int i1, const int i2) { return mat[i1]>mat[i2]; }
  18. };
  19. typedef std::priority_queue<int,std::vector<int>,greater> PQ;
  20.  
  21. // helps keeping code short and easy to understand
  22. #define CHECK(na) {if(mat[na] > mat[a]+input[na]) { mat[na] = mat[a]+input[na]; pq.push(na); }}
  23.  
  24. // returns minimal sum
  25. int dijkstra()
  26. {
  27.     PQ pq;
  28.     pq.push(0);
  29.     mat[0] = input[0];
  30.     while(!pq.empty())
  31.     {
  32.         int a = pq.top();
  33.         pq.pop();
  34.  
  35.         if(a>=cols) CHECK(a-cols) // up
  36.         if(a%cols!=0) CHECK(a-1) // left
  37.         if(a%cols!=(cols-1)) CHECK(a+1) // right
  38.         if(a<(rows-1)*cols) CHECK(a+cols) // down
  39.     }
  40.  
  41.     return mat[rows*cols-1];
  42. }
RAW Paste Data