1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5typedef struct {
6    int *data;
7    int size;
8    int capacity;
9} intVector;
10
11void push(intVector *vec, int val) {
12    if (vec->size == vec->capacity) {
13        vec->capacity *= 2;
14        vec->data = realloc(vec->data, vec->capacity * sizeof(int));
15    }
16    vec->data[vec->size++] = val;
17}
18
19int pop(intVector *vec) {
20    return vec->data[--vec->size];
21}
22
23int secondMinimum(int n, int edges[][2], int edgesSize, int time, int change) {
24    intVector *graph = malloc((n + 1) * sizeof(intVector));
25    for (int i = 1; i <= n; ++i) {
26        graph[i].data = malloc(10 * sizeof(int));
27        graph[i].size = 0;
28        graph[i].capacity = 10;
29    }
30    
31    for (int i = 0; i < edgesSize; ++i) {
32        push(&graph[edges[i][0]], edges[i][1]);
33        push(&graph[edges[i][1]], edges[i][0]);
34    }
35
36    int *first_min = malloc((n + 1) * sizeof(int));
37    int *second_min = malloc((n + 1) * sizeof(int));
38    
39    for (int i = 1; i <= n; ++i) {
40        first_min[i] = INT_MAX;
41        second_min[i] = INT_MAX;
42    }
43    first_min[1] = 0;
44
45    int pq[200000][2];
46    int pq_size = 0;
47    pq[pq_size][0] = 0;
48    pq[pq_size++][1] = 1;
49
50    while (pq_size > 0) {
51        int curr_time = pq[--pq_size][0];
52        int node = pq[pq_size][1];
53
54        for (int i = 0; i < graph[node].size; ++i) {
55            int neighbor = graph[node].data[i];
56            int wait_time = 0;
57            if ((curr_time / change) % 2 == 1) {
58                wait_time = change - (curr_time % change);
59            }
60            int new_time = curr_time + wait_time + time;
61
62            if (new_time < first_min[neighbor]) {
63                second_min[neighbor] = first_min[neighbor];
64                first_min[neighbor] = new_time;
65                pq[pq_size][0] = new_time;
66                pq[pq_size++][1] = neighbor;
67            } else if (new_time > first_min[neighbor] && new_time < second_min[neighbor]) {
68                second_min[neighbor] = new_time;
69                pq[pq_size][0] = new_time;
70                pq[pq_size++][1] = neighbor;
71            }
72        }
73    }
74
75    free(first_min);
76    free(second_min);
77    for (int i = 1; i <= n; ++i) {
78        free(graph[i].data);
79    }
80    free(graph);
81    return second_min[n];
82}

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];
}