algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

shortest-path-with-at-most-k-consecutive-identical-characters.cpp (2092B)


      1 class Solution {
      2 public:
      3 
      4     // priors is only for cycle detection, not necessary to memoize.
      5     int solve(int n, unordered_map<int,vector<pair<int,int>>> &edges, string labels, int k) {
      6 
      7         // djikstra's algo
      8             // push to heap with edges as found
      9                 // edge encoding:
     10                     // (cost, destination, consecutive)
     11         
     12         priority_queue<vector<int>> pq;
     13         pq.push({0,0,0});
     14 
     15         unordered_map<string,int> best {};
     16 
     17         // not super fast bc copies + string stuff, but it works.
     18         while(!pq.empty()) {
     19             vector<int> current = pq.top();
     20             vector<pair<int,int>>& el = edges[current[1]];
     21             int cCost = current[0];
     22             string cs = to_string(current[1]) + " " + to_string(current[2]);
     23             if(best.contains(cs)) {
     24                 if(best[cs] <= -cCost) {
     25                     pq.pop();
     26                     continue;
     27                 } else {
     28                     best[cs] = -cCost;
     29                 }
     30             } else {
     31                 best[cs] = -cCost;
     32             }
     33 
     34             if(current[1] == n-1) {
     35                 return -current[0];
     36             }
     37 
     38             for(int i = 0; i < el.size(); ++i) {
     39                 if(labels[current[1]] == labels[el[i].first]) {
     40                     int cons = current[2];
     41                     cons += 1;
     42                     if(cons >= k) {
     43                         continue;
     44                     }
     45                     pq.push({-el[i].second + cCost, el[i].first, cons});
     46                 } else {
     47                     pq.push({-el[i].second + cCost, el[i].first, 0});
     48                 }
     49             }
     50             pq.pop();
     51         }
     52         return -1;
     53 
     54 
     55     }
     56     int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
     57     
     58         unordered_map<int, vector<pair<int,int>>> edgeList {};
     59         for(int i = 0; i < edges.size(); ++i) {
     60             auto& current = edges[i];
     61             edgeList[current[0]].push_back({current[1], current[2]});
     62         }
     63 
     64         int res = solve(n,edgeList,labels,k);
     65 
     66         return res;
     67     }
     68 };