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}

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