Minimum Costs Using The Train Line - Leetcode Solution

Problem Statement:

You are given a 2D integer array, times, where each times[i] = [ui, vi, qi] denotes a train between train stations ui and vi that takes qi time units to travel.

You are also given two integers, n and target.

Return the minimum time required to travel from train station 1 to train station target. You can assume that there is at least one path that trains travel on that connects the two stations.

For Example:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, target = 4

Output: 2

Explanation:

The minimum time required to travel from train station 1 to train station 4 is 2. First, we take the train from station 1 to station 2, which takes 1 unit of time. Then we take another train from station 2 to station 4, which takes 1 unit of time. Therefore, the minimum time required is 2 units of time.

Solution:

To solve this problem, we first need to construct the graph using the given train routes. We can do this by using an adjacency list where the keys represent the stations and the values represent the connected stations along with the time required to travel from one station to another.

After constructing the graph, we can use Dijkstra's algorithm to find the shortest path between station 1 and the target station. We start by adding station 1 to a priority queue and set its distance as 0. We also initialize the distances of all other stations as infinity and add them to the priority queue.

We then loop through the priority queue while it is not empty. For each station in the queue, we loop through its connected stations and update their distances if the sum of the current station's distance and the time required to travel to the connected station is less than the connected station's current distance. We then add the connected station to the priority queue.

Once we are done iterating through all connected stations, we remove the current station from the priority queue. We repeat this process until we have reached the target station or the priority queue is empty.

At the end, we return the distance to the target station.

Pseudo Code:

// Construct graph for each train route [u, v, q] in times: add v to the adjacency list of u with weight q

// Initialize priority queue with source station priority_queue[] pq pq.push({0, 1})

// Initialize distances distances = [INF] * (n+1) distances[1] = 0

// Dijkstra's Algorithm while pq is not empty: current = pq.top().station pq.pop()

for each connected station in current's adjacency list:
    if distances[current] + weight < distances[connected]:
        distances[connected] = distances[current] + weight
        pq.push({distances[connected], connected})

// Return distance to target station return distances[target]

Time Complexity:

The time complexity of this solution is O(E log V), where E is the number of train routes and V is the number of stations. This is because we loop through all train routes to construct the graph, and then we use Dijkstra's algorithm to visit all connected stations. The priority queue ensures that we only visit each station once, and the log V factor comes from the fact that we are using a priority queue.

1