Second Minimum Time to Reach Destination

Leetcode Problem:

• Second Minimum Time to Reach Destination

Summary

• The problem is to find the second minimum time it will take to go from vertex 1 to vertex n in a bi-directional connected graph with n vertices, given the edges, time, and change.

Approach

• The approach used is to use a priority queue to keep track of the nodes to visit, and a visited array to keep track of the nodes that have been visited
• The time complexity is O(n log n) due to the use of the priority queue.

Complexity

• O(n log n)

Explain

• The solution code uses a priority queue to keep track of the nodes to visit, and a visited array to keep track of the nodes that have been visited
• The time complexity is O(n log n) due to the use of the priority queue
• The code first initializes the priority queue with the first node (1) and its time (0)
• Then, it enters a loop where it pops the node with the minimum time from the priority queue, and for each of its neighbors that have not been visited before, it adds them to the priority queue with their updated time
• The loop continues until all nodes have been visited
• Finally, it returns the minimum time that has been visited at least twice, which is the second minimum time.

Solution Code:

struct NODE {
    int num;
    int time;

    bool operator <(NODE &b){
        return time < b.time;
    }
};

template 
struct _heap{
    int size;
    T arr[80001];
    _heap(){
        size = 1;
    }
    bool cmp(T a, T b){
        return a < b;
    }
    bool empty(){
        return size == 1;
    }
    void push(T a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx], arr[idx/2])){
            T tmp = arr[idx];
            tmp = arr[idx/2];
            arr[idx/2] = tmp;
            idx /= 2;
        }
    }
    T pop(){
        T ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if (j >= size) break;
            if (j+1 < size && cmp(arr[j+1], arr[j])){
                j++;
            }
            if (cmp(arr[j], arr[i])){
                T tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i = j;
            } else{
                break;
            }
        }

        return ret;
    }
};

class Solution {
public:
    _heap h;
    vector visited[10001];
    vector adj[10001];
    int secondMinimum(int n, vector>& edges, int time, int change) {
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        visited[1].push_back(0);
        for(int i = 0 ; i < adj[1].size(); i++){
            int v = adj[1][i];
            h.push({v, time});
            visited[v].push_back(time);
        }
        int minCost = 1234567890;
        int minSecondCost = 1234567890;

        while(!h.empty()){
            NODE a = h.pop();
            if (a.num == n && a.time < minCost){
                minSecondCost = minCost;
                minCost = a.time;
            }
            if (a.num == n && a.time > minCost && minSecondCost > a.time){
                minSecondCost = a.time;
            }
            for(int i = 0 ; i < adj[a.num].size(); i++){
                int next = adj[a.num][i];
                if (visited[next].size() >= 2){
                    continue;
                }
                int cost = 0;
                if ((a.time / change)%2){
                    cost = (change - (a.time%change)) + a.time + time;
                } else {
                    cost = a.time + time;
                }

                if(visited[next].size() == 0){
                    visited[next].push_back(cost);
                } else{
                    if (visited[next][0] == cost){
                        continue;
                    }
                    visited[next].push_back(cost);
                }
                h.push({next, cost});
            }
        }
        return minSecondCost;
    }
};