2045. 到达目的地的第二短时间 - 力扣（LeetCode） (leetcode-cn.com)
题目
城市用一个 双向连通 图表示，图中有 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的次短路径。
思路
最短路的变种，次短路径。
注意题目每一条路的时间固定，并且节点有红绿灯，只有绿灯能通行，需要判断当前节点是否为绿灯，不是绿灯则需要等待。
dijkstra求最短路，每次是维护一个数组dis[i]，表示起点到当前节点i的最短距离(此题距离等于题目描述的时间)。那么类似于求次小值的思想，可以再维护一个数组dis1[i]，表示表示起点到当前节点i的次短距离，次短距离需要严格小于最短距离。相比于求最短路径只是多维护了一个数组。
并且如果当前节点是红灯，那么需要等待至绿灯。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include "iostream"
#include "vector"
#include "cstring"
#include "queue"
#include "algorithm"
using namespace std;
struct edge {
int v, d;
edge(int cv, int cd) : v(cv), d(cd) {}
};
class Solution {
public:
static const int maxn = 1e4 + 10;
int d[maxn], d2[maxn];
vector<edge> e[maxn];
int secondMinimum(int n, vector<vector<int>> &edges, int time, int change) {
for (auto &x: edges) {
e[x[0]].emplace_back(time, x[1]);
e[x[1]].emplace_back(time, x[0]);
}
dijkstra(1, n, change);
return d2[n];
}
void dijkstra(int s, int n, int change) {
memset(d, 0x7f, sizeof d);
memset(d2, 0x7f, sizeof d2);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;
d[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
pair<int, int> p = que.top();
que.pop();
if (p.first > d2[p.second]) continue;
if ((p.first / change) & 1) p.first =p.first+ change-p.first%change;
for (int i = 0; i < e[p.second].size(); i++) {
int v = p.first + e[p.second][i].v;
int dd = e[p.second][i].d;
if (v < d[dd]) {
swap(d[dd], v);
que.emplace(d[dd], dd);
}
if (v > d[dd] && v < d2[dd]) {
d2[dd] = v;
que.emplace(v, dd);
}
}
}
}
};
|