LeetCode 1928: Minimum Cost to Reach Destination in Time Solution

Master LeetCode problem 1928 (Minimum Cost to Reach Destination in Time), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1928. Minimum Cost to Reach Destination in Time

Hard

Array Dynamic Programming Graph

Problem Explanation

Explanation

To solve this problem, we can use Dijkstra's algorithm with a slight modification to keep track of the total time taken as well as the total cost incurred at each city. We will initialize our priority queue with the starting city (city 0) and maintain a visited set to avoid revisiting cities unnecessarily.

Start by creating a priority queue to store the current city, total time taken, and total cost incurred at that city.
Initialize the priority queue with (city 0, time 0, cost 0) and add it to the visited set.
While the priority queue is not empty:
- Pop the top element from the priority queue.
- If the current city is the destination city (city n-1) and the total time taken is less than or equal to maxTime, return the total cost incurred.
- Iterate through all the neighboring cities of the current city:
  - Calculate the new time taken and cost incurred if we choose to travel to the neighboring city.
  - If the neighboring city has not been visited or the new time taken is less than the previously recorded time taken at that city, update the information and add it to the priority queue.
If we reach this point, it means we cannot reach the destination city within the given maxTime, so return -1.

Time Complexity: The time complexity of this algorithm is O(E * log(V)), where E is the number of edges and V is the number of vertices.

Space Complexity: The space complexity of this algorithm is O(V) for the priority queue and visited set.

Solution Code

import java.util.*;

class City {
    int id;
    int time;
    int cost;

    public City(int id, int time, int cost) {
        this.id = id;
        this.time = time;
        this.cost = cost;
    }
}

class Solution {
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], x -> new ArrayList<>()).add(new int[]{edge[1], edge[2]});
            graph.computeIfAbsent(edge[1], x -> new ArrayList<>()).add(new int[]{edge[0], edge[2]});
        }

        PriorityQueue<City> pq = new PriorityQueue<>(Comparator.comparingInt(c -> c.time));
        Set<Integer> visited = new HashSet<>();

        pq.offer(new City(0, 0, passingFees[0]);

        while (!pq.isEmpty()) {
            City currCity = pq.poll();
            int cityId = currCity.id;
            int time = currCity.time;
            int cost = currCity.cost;

            if (cityId == n - 1 && time <= maxTime) {
                return cost;
            }

            visited.add(cityId);

            for (int[] neighbor : graph.getOrDefault(cityId, new ArrayList<>())) {
                int nextCity = neighbor[0];
                int newTime = time + neighbor[1];
                int newCost = cost + passingFees[nextCity];

                if (newTime <= maxTime && (!visited.contains(nextCity) || newTime < time)) {
                    pq.offer(new City(nextCity, newTime, newCost));
                }
            }
        }

        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1928 (Minimum Cost to Reach Destination in Time)?

This page provides optimized solutions for LeetCode problem 1928 (Minimum Cost to Reach Destination in Time) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1928 (Minimum Cost to Reach Destination in Time)?

The time complexity for LeetCode 1928 (Minimum Cost to Reach Destination in Time) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1928 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1928 in Java, C++, or Python.

Back to LeetCode Solutions