每日一题 0124

（2022.01.24）每日一题：到达目的地的第二短时间 （×）

遇到困难睡大觉！哎，基础太差，直奔官方题解

方法一：广度优先搜索

需要补充的知识点：

1. 求解权重相同的最短路径问题可以采用广度优先（BFS）
2. 严格次短路径的概念

思路与算法:

? 因为任意路径所花费的时间是相同的，所以路径越长，所需时间越久。求到达目的地的严格次短路径，就可以直接计算到达目的地的第二短时间。

? 这里可知知识点一，但进行修改，使用BFS求解最短路径时，经过的点与初始点的路径长度是所有未搜索过的路径中的最小值，第一次访问到的节点的路径一定是最短的！（而DFS并不能保证这一点？这是我自己的理解，貌似是的。）

class Solution {
public:
    int secondMinimum(int n, vector>& edges, int time, int change) {
        vector> graph(n + 1);
        for (auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        // int index = 0;
        // for (auto &t :graph){
        //     std::cout<<"idx:"<> path(n + 1, vector(2, INT_MAX));
        path[1][0] = 0;
        queue> q;
        q.push({1, 0});
        while (path[n][1] == INT_MAX) {
            auto [cur, len] = q.front();
            q.pop();
            for (auto next : graph[cur]) {
                if (len + 1 < path[next][0]) {
                    path[next][0] = len + 1;
                    q.push({next, len + 1});
                } else if (len + 1 > path[next][0] && len + 1 < path[next][1]) {
                    path[next][1] = len + 1;
                    q.push({next, len + 1});
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < path[n][1]; i++) {
            if (ret % (2 * change) >= change) {
                ret = ret + (2 * change - ret % (2 * change));
            }
            ret = ret + time;
        }
        return ret;
    }
};