# Problem Understanding In this problem, we are given a set of $N$ cities and $M$ one-way magical portals where each portal connects two cities and has an associated travel time. The cities are numbered from $1$ to $N$. Our goal is to determine the minimum amount of time required to travel from city $1$ to city $N$. If there is no valid route, we must output $-1$. Essentially, the cities and portals form a directed weighted graph where: - Each node represents a city. - Each directed edge represents a portal with a cost (or weight) corresponding to its travel time. Thus, the problem reduces to finding the shortest path in a directed graph from node $1$ to node $N$. # Approach Since the weights (travel times) of the portals are non-negative (time cannot be negative), we can utilize Dijkstra's algorithm which efficiently finds the shortest path in a graph with non-negative edge weights. The approach is as follows: 1. **Graph Representation**: Build an adjacency list where each entry for city $i$ contains tuples representing connected cities and the travel time. 2. **Priority Queue (Min-Heap)**: Use a min-heap to always extract the city with the smallest current travel time. 3. **Relaxation**: For each portal from the current city, check if the path via this portal provides a shorter time to reach the destination city and update accordingly. 4. **Termination**: Continue until the destination city $N$ is reached or the queue is empty. If city $N$ is not reached, output $-1$. This approach leverages the greedy nature of Dijkstra’s algorithm to continuously explore the most promising next city until the destination is either reached with the minimum possible travel time or determined to be unreachable. # Time and Space Complexity Analysis - **Time Complexity**: - Constructing the adjacency list from input takes $O(M)$ time. - The main loop of Dijkstra's algorithm executes in $O((N + M)\,\log N)$ time because each vertex is inserted into the priority queue and each edge is processed. - Thus, the overall time complexity is $O((N + M)\,\log N)$. - **Space Complexity**: - The adjacency list requires $O(N + M)$ space. - The distance array and the priority queue will need additional $O(N)$ space in the worst case. - Overall, the space complexity is $O(N + M)$.