Second Minimum Time to Reach Destination

Shortest Path, Dijkstra’s algorithm

Original Link

Solution

In this problem, we should find the second minimum shortest path to the destination. If the problem wants the minimum shortest path, it would be solved with Dijkstra's algorithm. However, we should do more to find the second one.

One thing we can do is to put all possible paths until we reach the destination twice at different times. Unlike Dijkstra’s algorithm, we don’t need to compare the minimum times to get to the next vertex. If we use min-heap, the answer will be returned as expected.

The solution above takes too long because it contains too many duplicates to reach each vertex. So, we reduce the duplication to make it faster.

If we get to the vertex X at time Y, then we don’t need to revisit X with time Y because the answer after that will be the same. For example, if the minimum path from 1 to N is 1 → 4 → N and we visited vertex 4 at time 10. Then, we don’t need to revisit vertex 4 at time 10 from vertice other than 1 because even though the routes are different, time to N will be the same.

So, we can remove the case where we visited the vertex X with the time Y. Also, we only need to get the second minimum, meaning we don’t need to get the third minimum time to visit each vertex.

class Solution {
public:
    // Adjacency list representation of the graph
    unordered_map<int, vector<int>> graph;

    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {   
        // Build the graph from the given edge list
        for (auto & edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        // Priority queue for Dijkstra-like traversal (min-heap)
        priority_queue<pair<int, int>> pq;
        pq.push({0, 1});  // {travel time, node}

        // Store up to two shortest arrival times at each node
        vector<vector<int>> arrivalTimes(n + 1);
        arrivalTimes[1].push_back(0);  // Start at node 1 with time 0

        while (!pq.empty()) { 
            auto current = pq.top();
            pq.pop();
            int travelTime = -current.first;  // Negating since we use max-heap simulation
            int node = current.second;

            // If we reach the destination and recorded the second arrival time, return it
            if (node == n && arrivalTimes[node].size() == 2) {
                return arrivalTimes[node].back();
            }

            // Handle traffic signal: Wait if the light is red
            if ((travelTime / change) % 2 == 1) {
                travelTime = change * ((travelTime / change) + 1);  // Wait until green
            }

            // Explore all adjacent nodes
            for (auto & neighbor : graph[node]) {
                int newTime = travelTime + time;

                // If the neighbor already has two recorded times, ignore
                if (arrivalTimes[neighbor].size() > 1) continue;

                // Ensure we record two **distinct** times per node
                if (!arrivalTimes[neighbor].empty() && arrivalTimes[neighbor].back() == newTime) continue;

                // Store new travel time and push to queue
                arrivalTimes[neighbor].push_back(newTime);
                pq.push({-newTime, neighbor});  // Use negative to simulate min-heap
            }
        }

        return -1;  // Should never be reached if a second minimum path exists
    }
};

Time Complexity Analysis:

• Graph Construction: O(E), where E is the number of edges.

• Priority Queue Operations:

  • Each node can be pushed into the queue at most twice (O(2N log N) ~ O(N log N)).

  • Each edge is processed at most twice (O(2E)).

• Overall Complexity: O((N + E) log N), which is efficient for large graphs.