题目
城市用一个 双向连通 图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。
每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都 同时 改变。你可以在 任何时候 进入某个节点，但是 只能 在节点 信号灯是绿色时 才能离开。如果信号灯是 绿色 ，你 不能 在节点等待，必须离开。
第二小的值 是 严格大于 最小值的所有值中最小的值。
- 例如，[2, 3, 4] 中第二小的值是 3 ，而 [2, 2, 4] 中第二小的值是 4 。
给你 n、edges、time 和 change ，返回从节点 1 到节点 n 需要的 第二短时间 。
注意：
- 你可以 任意次 穿过任意顶点，包括 1 和 n 。
- 你可以假设在 启程时 ，所有信号灯刚刚变成 绿色 。
示例 1：
|
输入：n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5 输出：13 解释： 上面的左图展现了给出的城市交通图。 右图中的蓝色路径是最短时间路径。 花费的时间是： - 从节点 1 开始，总花费时间=0 - 1 -> 4：3 分钟，总花费时间=3 - 4 -> 5：3 分钟，总花费时间=6 因此需要的最小时间是 6 分钟。 右图中的红色路径是第二短时间路径。 - 从节点 1 开始，总花费时间=0 - 1 -> 3：3 分钟，总花费时间=3 - 3 -> 4：3 分钟，总花费时间=6 - 在节点 4 等待 4 分钟，总花费时间=10 - 4 -> 5：3 分钟，总花费时间=13 因此第二短时间是 13 分钟。
示例 2：
输入：n = 2, edges = [[1,2]], time = 3, change = 2 输出：11 解释： 最短时间路径是 1 -> 2 ，总花费时间 = 3 分钟 最短时间路径是 1 -> 2 -> 1 -> 2 ，总花费时间 = 11 分钟
解题
方法一：BFS
由于time 和 change 是固定的，经过多少条边就知道花费了多少时间。因此这题本质上可以看成边权均为 1 的图，我们要求的就是 1 到 n的严格次短路的长度，知道长度就知道花费的时间。
通过bfs，维护每个顶点 的 最短路径和次短路径 即可。
由于是bfs，队列中，存的路径长度是越来越长的。因此一但遇到次短路径，就可以返回。因为后续只可能是路径越来越长的,所以不会存在第二次更新最小值和次小值（时间复杂度上得以保证）。
class Solution { public: int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) { //创建邻接表 vector<vector<int>> graph(n+1); for(auto &e:edges){ graph[e[0]].push_back(e[1]); graph[e[1]].push_back(e[0]); } // path[i][0] 表示从 1 到 i 的最短路长度，path[i][1] 表示从 1 到 i 的严格次短路长度 vector<vector<int>> path(n+1,vector<int>(2,INT_MAX)); path[1][0]=0; queue<pair<int,int>> q; q.push({1,0}); while(path[n][1]==INT_MAX){ auto [cur,len]=q.front(); q.pop(); for(int 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 res=0; for(int i=0;i<path[n][1];i++){ if(res%(2*change)>=change){ res=res+2*change-res%(2*change); } res+=time; } return res; } };
