2045. Second Minimum Time to Reach Destination

[mah-shamim]

A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes.

Each vertex has a traffic signal which changes its color from green to red and vice versa every change minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green.

The second minimum value is defined as the smallest value strictly larger than the minimum value.

• For example the second minimum value of [2, 3, 4] is 3, and the second minimum value of [2, 2, 4] is 4.

Given n, edges, time, and change, return the second minimum time it will take to go from vertex 1 to vertex n.

Notes:

• You can go through any vertex any number of times, including 1 and n.
• You can assume that when the journey starts, all signals have just turned green.

Example 1:

• Input: n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5

• Output: [7,0,8]

• Explanation:
  The figure on the left shows the given graph.
  The blue path in the figure on the right is the minimum time path.
  The time taken is:

  • Start at 1, time elapsed=0
  • 1 -> 4: 3 minutes, time elapsed=3
  • 4 -> 5: 3 minutes, time elapsed=6
    Hence the minimum time needed is 6 minutes.

  The red path shows the path to get the second minimum time.

  • Start at 1, time elapsed=0
  • 1 -> 3: 3 minutes, time elapsed=3
  • 3 -> 4: 3 minutes, time elapsed=6
  • Wait at 4 for 4 minutes, time elapsed=10
  • 4 -> 5: 3 minutes, time elapsed=13
    Hence the second minimum time is 13 minutes.

Example 2:

• Input: n = 2, edges = [[1,2]], time = 3, change = 2
• Output: 11
• Explanation:
  The minimum time path is 1 -> 2 with time = 3 minutes.
  The second minimum time path is 1 -> 2 -> 1 -> 2 with time = 11 minutes.

Constraints:

• 2 <= n <= 104
• n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)
• edges[i].length == 2
• 1 <= ui, vi <= n
• ui != vi
• There are no duplicate edges.
• Each vertex can be reached directly or indirectly from every other vertex.
• 1 <= time, change <= 103

Hint:

1. How much is change actually necessary while calculating the required path?
2. How many extra edges do we need to add to the shortest path?

[mah-shamim]

To solve this problem, we can follow these steps:

1. Model the Graph: Represent the graph using an adjacency list.
2. Modified BFS: Use a BFS-like approach but keep track of the time taken to reach each node. Maintain a queue that stores the current node and the time at which it was reached.
3. Track Minimum Times: Use an array to store the minimum and second minimum times to reach each node.
4. Consider Traffic Signals: When traversing to the next node, calculate the waiting time if the signal is red at the moment of arrival.

Let's implement this solution in PHP: 2045. Second Minimum Time to Reach Destination

<?PHP

    /**
     * @param Integer $n
     * @param Integer[][] $edges
     * @param Integer $time
     * @param Integer $change
     * @return Integer
     */
    function secondMinimum($n, $edges, $time, $change) {
        $graph = array_fill(0, $n + 1, []);
        $queue = [];
        $queue[] = [1, 0]; // initial position
        
        // minTime[i][0] := the first minimum time to reach the node i
        // minTime[i][1] := the second minimum time to reach the node i
        $minTime = array_fill(0, $n + 1, [PHP_INT_MAX, PHP_INT_MAX]);
        $minTime[1][0] = 0;

        foreach ($edges as $edge) {
            $u = $edge[0];
            $v = $edge[1];
            $graph[$u][] = $v;
            $graph[$v][] = $u;
        }

        while (!empty($queue)) {
            [$i, $prevTime] = array_shift($queue);
            // Start from green.
            // If `numChangeSignal` is odd, now red.
            // If `numChangeSignal` is even, now green.
            $numChangeSignal = intdiv($prevTime, $change);
            $waitTime = $numChangeSignal % 2 === 0 ? 0 : $change - $prevTime % $change;
            $newTime = $prevTime + $waitTime + $time;

            foreach ($graph[$i] as $j) {
                if ($newTime < $minTime[$j][0]) {
                    $minTime[$j][0] = $newTime;
                    $queue[] = [$j, $newTime];
                } elseif ($minTime[$j][0] < $newTime && $newTime < $minTime[$j][1]) {
                    if ($j === $n) {
                        return $newTime;
                    }
                    $minTime[$j][1] = $newTime;
                    $queue[] = [$j, $newTime];
                }
            }
        }

        throw new Exception("Unable to find the second minimum time");
    }

// Example usage
$solution = new Solution();
$n = 5;
$edges = [[1, 2], [1, 3], [1, 4], [3, 4], [4, 5]];
$time = 3;
$change = 5;
echo $solution->secondMinimum($n, $edges, $time, $change) . "\n"; // Output: 13

$n = 2;
$edges = [[1, 2]];
$time = 3;
$change = 2;
echo $solution->secondMinimum($n, $edges, $time, $change) . "\n"; // Output: 11

?>

Explanation:

1. Graph Representation: We initialize the graph as an adjacency list using a 2D array.
2. Initialization:
   • minTime array is initialized with PHP's PHP_INT_MAX to simulate infinite time.
   • minTime[1][0] is set to 0 because the start vertex (1) has a travel time of 0.
3. Queue Setup: We use SplQueue for BFS and enqueue the starting node and time.
4. BFS Traversal:
   • For each node, compute the wait time if the signal is red.
   • Calculate the newTime it would take to move to each neighbor.
   • Update the minTime array and enqueue the new state if it's either a new minimum or a second minimum.
5. Return the Result: Once the second minimum time to reach node n is found, return it.