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
| class Solution {
public int secondMinimum(int n, int[][] edges, int time, int change) {
List<Integer>[] g = new ArrayList[n + 1];
Arrays.setAll(g, k -> new ArrayList<>());
for (int[] e : edges) {
g[e[0]].add(e[1]);
g[e[1]].add(e[0]);
}
int[][] path = new int[n + 1][2];
for (int i = 0; i <= n; i++) {
Arrays.fill(path[i], Integer.MAX_VALUE);
}
path[1][0] = 0;
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{1, 0});
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int cur = arr[0], len = arr[1];
for (int next : g[cur]) {
if (len + 1 < path[next][0]) {
path[next][0] = len + 1;
queue.offer(new int[]{next, len + 1});
} else if (len + 1 > path[next][0] && len + 1 < path[next][1]) {
path[next][1] = len + 1;
queue.offer(new int[]{next, len + 1});
}
}
}
int ans = 0;
for (int i = 0; i < path[n][1]; ++i) {
if (ans % (2 * change) >= change) {
ans = ans + (2 * change - ans % (2 * change));
}
ans += time;
}
return ans;
}
}
|
wechat
