1import java.util.*;
2
3public class SecondMinimumTime {
4    public int secondMinimum(int n, int[][] edges, int time, int change) {
5        List<Integer>[] graph = new ArrayList[n + 1];
6        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
7        for (int[] edge : edges) {
8            graph[edge[0]].add(edge[1]);
9            graph[edge[1]].add(edge[0]);
10        }
11
12        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
13        pq.offer(new int[]{0, 1}); // (current_time, node)
14        int[] minTime = new int[n + 1];
15        int[] secondMinTime = new int[n + 1];
16        Arrays.fill(minTime, Integer.MAX_VALUE);
17        Arrays.fill(secondMinTime, Integer.MAX_VALUE);
18        minTime[1] = 0;
19
20        while (!pq.isEmpty()) {
21            int[] current = pq.poll();
22            int currTime = current[0], node = current[1];
23
24            for (int neighbor : graph[node]) {
25                int waitTime = 0;
26                if ((currTime / change) % 2 == 1) {
27                    waitTime = change - (currTime % change);
28                }
29                int newTime = currTime + waitTime + time;
30
31                if (newTime < minTime[neighbor]) {
32                    secondMinTime[neighbor] = minTime[neighbor];
33                    minTime[neighbor] = newTime;
34                    pq.offer(new int[]{newTime, neighbor});
35                } else if (newTime < secondMinTime[neighbor] && newTime > minTime[neighbor]) {
36                    secondMinTime[neighbor] = newTime;
37                    pq.offer(new int[]{newTime, neighbor});
38                }
39            }
40        }
41
42        return secondMinTime[n];
43    }
44}

1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>

using namespace std;

int secondMinimumBFS(int n, vector<vector<int>>& edges, int time, int change) {
    vector<vector<int>> graph(n + 1);
    for (const auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    vector<int> first_min(n + 1, INT_MAX);
    vector<int> second_min(n + 1, INT_MAX);
    queue<pair<int, int>> q;
    q.push({0, 1});
    first_min[1] = 0;

    while (!q.empty()) {
        auto [curr_time, node] = q.front();
        q.pop();

        for (int neighbor : graph[node]) {
            int wait_time = 0;
            if ((curr_time / change) % 2 == 1) {
                wait_time = change - (curr_time % change);
            }
            int new_time = curr_time + wait_time + time;

            if (new_time < first_min[neighbor]) {
                second_min[neighbor] = first_min[neighbor];
                first_min[neighbor] = new_time;
                q.push({new_time, neighbor});
            } else if (new_time > first_min[neighbor] && new_time < second_min[neighbor]) {
                second_min[neighbor] = new_time;
                q.push({new_time, neighbor});
            }
        }
    }

    return second_min[n];
}