Untitled

class Solution {
public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        vector<vector<pair<int, int>>> G;
        G.assign(n + 1, {});
        for (vector<int> &e : edges) {
            G[e[0]].emplace_back(e[1], time);
            G[e[1]].emplace_back(e[0], time);
        }
        vector<int> visited(G.size(), -1);
        auto [SPN, minimum] = BFS(visited, G, n, time, change);
        int secondMinimum;
        if (sameLevel(visited, G, SPN)) {
            secondMinimum = minimum + isRedLight(minimum, change) + time;
        }
        else secondMinimum = minimum + isRedLight(minimum, change) + time + isRedLight(minimum + isRedLight(minimum, change) + time, change) + time;
        return secondMinimum;
    }

    pair<unordered_map<int, bool>, int> BFS(vector<int> &visited, vector<vector<pair<int, int>>> &G, int t, int time, int change) {
        using QueuePair = tuple<int, int, int>; // cost, level, node
        priority_queue<QueuePair, vector<QueuePair>, greater<QueuePair>> Q;
        Q.emplace(make_tuple(0, 0, 1));
        int minimum = INT_MAX;
        while (!Q.empty()) {
            auto [costU, levelU, u] = Q.top();
            Q.pop();
            if (visited[u]!=-1) continue;
            visited[u] = levelU;
            for (auto &[v, cost] : G[u]) {
                int trafficLightCost = isRedLight(costU + cost, change);
                int costV = costU + cost;
                if (v == t && minimum == INT_MAX) minimum = costV;
                Q.emplace(costV + trafficLightCost, levelU + 1, v);
            }
        }
        unordered_map<int, bool> SPN;
        Q.emplace(make_tuple(-1, 0, t));
        SPN[t] = true;
        while (!Q.empty()) {
            auto [costU, levelU, u] = Q.top();
            Q.pop();
            for (auto &[v, cost] : G[u]) {
                if (visited[v] == visited[u] - 1) {
                    SPN[v] = true;
                    Q.emplace(-1, levelU + 1, v);
                }
            }
        }
        // for (auto v : SPN) {
        //     cout << v << " ";
        // }
        return pair{SPN, minimum};
    }
    int isRedLight(int time, int change) {
        // 0 ~ change - 1 -> green
        // change ~ 2 * change - 1 -> red
        // 2 * change ~ 3 * change - 1 -> green
        // 3 * change ~ 4 * change - 1 -> red
        // 4 ~ 7, 12 ~ 15, 20 ~ 23
        // change <= % 2 * change <= 2 & change - 1
        if (change <= time % (2 * change) && time % (2 * change) <= 2 * change - 1) {
            return 2 * change - time % (2 * change);
        }
        return 0;
    }
    bool sameLevel(vector<int> &visited, vector<vector<pair<int, int>>> &G, unordered_map<int, bool> &SPN) {
        for (auto &node : SPN) {
            int u = node.first;
            for (auto &[v, cost] : G[u]) {
                if (visited[v] == visited[u])
                    return true;
            }
        }
        return false;
    }
};