1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>
5
6using namespace std;
7
8int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
9    vector<vector<int>> graph(n + 1);
10    for (const auto& edge : edges) {
11        graph[edge[0]].push_back(edge[1]);
12        graph[edge[1]].push_back(edge[0]);
13    }
14
15    vector<int> first_min(n + 1, INT_MAX);
16    vector<int> second_min(n + 1, INT_MAX);
17    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
18    pq.emplace(0, 1);
19    first_min[1] = 0;
20
21    while (!pq.empty()) {
22        auto [curr_time, node] = pq.top();
23        pq.pop();
24
25        for (int neighbor : graph[node]) {
26            int wait_time = 0;
27            if ((curr_time / change) % 2 == 1) {
28                wait_time = change - (curr_time % change);
29            }
30            int new_time = curr_time + wait_time + time;
31
32            if (new_time < first_min[neighbor]) {
33                second_min[neighbor] = first_min[neighbor];
34                first_min[neighbor] = new_time;
35                pq.emplace(new_time, neighbor);
36            } else if (new_time > first_min[neighbor] && new_time < second_min[neighbor]) {
37                second_min[neighbor] = new_time;
38                pq.emplace(new_time, neighbor);
39            }
40        }
41    }
42
43    return second_min[n];
44}

1using System;
2using System.Collections.Generic;
3
4public class Solution {
    public int SecondMinimum(int n, int[][] edges, int time, int change) {
        var graph = new List<int>[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new List<int>();

        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        var firstMinTime = new int[n + 1];
        var secondMinTime = new int[n + 1];
        Array.Fill(firstMinTime, int.MaxValue);
        Array.Fill(secondMinTime, int.MaxValue);
        firstMinTime[1] = 0;

        var queue = new Queue<(int, int)>(); // (current_time, node)
        queue.Enqueue((0, 1));

        while (queue.Count > 0) {
            var (currTime, currNode) = queue.Dequeue();

            foreach (var neighbor in graph[currNode]) {
                int waitTime = 0;
                if ((currTime / change) % 2 == 1) {
                    waitTime = change - (currTime % change);
                }
                int newTime = currTime + waitTime + time;

                if (newTime < firstMinTime[neighbor]) {
                    secondMinTime[neighbor] = firstMinTime[neighbor];
                    firstMinTime[neighbor] = newTime;
                    queue.Enqueue((newTime, neighbor));
                } else if (newTime > firstMinTime[neighbor] && newTime < secondMinTime[neighbor]) {
                    secondMinTime[neighbor] = newTime;
                    queue.Enqueue((newTime, neighbor));
                }
            }
        }

        return secondMinTime[n];
    }
}