Leet Code Daily 2024-07-28 - Second Minimum Time to Reach Destination

constexpr int kVeryLong = 100000000;

class Solution {
public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {

        auto neighborhood = vector<vector<int>>(n);
        for (const auto& edge : edges) {
            neighborhood[edge[0] - 1].push_back(edge[1] - 1);
            neighborhood[edge[1] - 1].push_back(edge[0] - 1);
        }
        auto leave_time = [&](int arrive_time) {
            const int t = arrive_time % (change * 2);
            return (t < change) ? arrive_time : (arrive_time - t + change * 2);
        };

        auto arrive_time =
            vector<pair<int, int>>(n, make_pair(kVeryLong, kVeryLong));
        arrive_time[0] = make_pair(0, kVeryLong);

        auto in_queue = vector<bool>(n, false);

        queue<int> queue;
        queue.push(0);
        in_queue[0] = true;

        for (; !queue.empty(); queue.pop()) {
            auto u = queue.front();
            in_queue[u] = false;
            for (const auto v : neighborhood[u]) {
                auto candidates = vector<int>({
                    arrive_time[v].first,
                    arrive_time[v].second,
                    leave_time(arrive_time[u].first) + time,
                    leave_time(arrive_time[u].second) + time,
                });
                sort(candidates.begin(), candidates.end());
                candidates.erase(unique(candidates.begin(), candidates.end()),
                                 candidates.end());
                auto new_arrive_time = make_pair(candidates[0], candidates[1]);
                if (new_arrive_time != arrive_time[v]) {
                    arrive_time[v] = new_arrive_time;
                    if (!in_queue[v]) {
                        queue.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }

        return arrive_time[n - 1].second;
    }
};