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 };