Shortest Path With At Most K Consecutive Identical Characters

class State {
public:
    char label;
    int count;
    int total;

    bool operator<(const State& other) const {
        if (total != other.total) {
            return total < other.total;
        } else if (count != other.count) {
            return count < other.count;
        } else {
            return label < other.label;
        }
    }
};

class Solution {
public:
    int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
        vector<vector<pair<int, int>>> adjacency_list(n);

        for (vector<int>& edge : edges) {
            adjacency_list[edge[0]].push_back({edge[1], edge[2]});
        }

        vector<vector<long long>> dist(
            n, vector<long long>(k + 1, LLONG_MAX)
        );
        dist[0][1] = 0;
        State curr{labels[0], 1, 0};

        priority_queue<pair<State, int>, vector<pair<State, int>>, greater<pair<State, int>>> pq;
        pq.push({curr, 0});

        while (!pq.empty()) {
            auto top = pq.top();
            if (top.second == n-1) {
                return top.first.total;
            }
            pq.pop();
            if (top.first.total != dist[top.second][top.first.count]) continue;

            for (int i = 0; i < adjacency_list[top.second].size(); ++i) {
                char curr_letter = top.first.label;
                int curr_count = top.first.count;
                int curr_total = top.first.total;
                int target = adjacency_list[top.second][i].first;
                int weight = adjacency_list[top.second][i].second;

                if (curr_letter != labels[target]) {
                    curr_count = 1;
                } else if (curr_count < k) {
                    ++curr_count;
                } else {
                    continue;
                }

                if (curr_total + weight < dist[target][curr_count]) {
                    dist[target][curr_count] = curr_total + weight;
                    pq.push({State(labels[target], curr_count, curr_total + weight), target});
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
  int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
    // start off w/ `using` to simplify problem (don't need to create classes half the time)
    using Cost = long long;
    using Edge = pair<int, int>;
    using Entry = tuple<Cost, int, int>;

    vector<vector<Edge>> graph(n);
    for (const auto& edge : edges) {
      graph[edge[0]].emplace_back(edge[1], edge[2]);
    }

    constexpr Cost INF = numeric_limits<Cost>::max();
    vector<vector<Cost>> distance(n, vector<Cost>(k+1, INF));

    priority_queue<Entry, vector<Entry>, greater<Entry>> frontier;

    distance[0][1] = 0;
    frontier.emplace(0, 0, 1);

    while (!frontier.empty()) {
      const auto [cost, node, runLength] = frontier.top();
      frontier.pop();

      if (cost != distance[node][runLength]) {
        continue;
      }

      if (node == n-1) {
        return static_cast<int>(cost);
      }

      for (const auto& [next, weight] : graph[node]) {
        const int nextRunLength = labels[node] == labels[next] ? runLength + 1 : 1;

        if (nextRunLength > k) {
          continue;
        }

        const Cost nextCost = cost + weight;
        if (nextCost >= distance[next][nextRunLength]) {
          continue;
        }

        distance[next][nextRunLength] = nextCost;
        frontier.emplace(nextCost, next, nextRunLength);
      }
    }

    return -1;
  }
};