Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Minimum Cost to Reach Destination in Time solution and explanation

HardArrayDynamic ProgrammingGraph8 min read42.6% acceptanceUpdated 9 Apr 2026
Asked atAirbnbDatabricksAmazonMicrosoftMetaGoogle
Practise Minimum Cost to Reach Destination in Time
21:59
LeetCode 1928. Minimum Cost to Reach Destination in TimeHappy Coding · 21:59 · 5K viewsWatch on YouTube
9 more videos on this problem
  1. LeetCode 1928. Minimum Cost to Reach Destination in TimeHappy Coding · 21:59 · 5K views
  2. Minimum Cost to Reach Destination in Time | Leetcode 1928 | DIJKSTRA'S |proteinCoder · 6:28 · 1K views
  3. [English] LeetCode 1928. Minimum Cost to Reach Destination in Timehappygirlzt · 12:05 · 910 views
  4. 1928. Minimum Cost to Reach Destination in Time (Leetcode Hard)Programming Live with Larry · 58:32 · 892 views
  5. Leetcode 1928. Minimum Cost to Reach Destination in TimeElite Code · 26:53 · 875 views
  6. 1928. Minimum Cost to Reach Destination in Time (Solution 2) - Daily Leetcode (Day 17)yeetcode · 26:19 · 873 views
  7. 1928. Minimum Cost to Reach Destination in Time (Solution 1) - Daily Leetcode (Day 15)yeetcode · 19:27 · 738 views
  8. Leetcode 1928. Minimum Cost to Reach Destination in Time | Java | Dijkstra's algorithmJeezy Leets · 17:49 · 177 views
  9. #LC-1928#Minimum Cost to Reach in Time #DECODE DSA # LEVEL UP#MISCELLANEOUS #leetcode#challengeDecode · 12:16 · 173 views
  10. leetcode 1928 Minimum Cost to Reach Destination in Time | Dijkstra's algorithm with 2 relaxationsCode-Yao · 17:10 · 159 views

The problem

There is a country of n cities numbered from 0 to n - 1 where all the cities are connected by bi-directional roads. The roads are represented as a 2D integer array edges where edges[i] = [xi, yi, timei] denotes a road between cities xi and yi that takes timei minutes to travel. There may be multiple roads of differing travel times connecting the same two cities, but no road connects a city to itself.

Each time you pass through a city, you must pay a passing fee. This is represented as a 0-indexed integer array passingFees of length n where passingFees[j] is the amount of dollars you must pay when you pass through city j.

In the beginning, you are at city 0 and want to reach city n - 1 in maxTime minutes or less. The cost of your journey is the summation of passing fees for each city that you passed through at some moment of your journey (including the source and destination cities).

Given maxTime, edges, and passingFees, return the minimum cost to complete your journey, or -1 if you cannot complete it within maxTime minutes.

Example 1:

Input: maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: 11
Explanation: The path to take is 0 -> 1 -> 2 -> 5, which takes 30 minutes and has $11 worth of passing fees.

Example 2:

Input: maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: 48
Explanation: The path to take is 0 -> 3 -> 4 -> 5, which takes 26 minutes and has $48 worth of passing fees.
You cannot take path 0 -> 1 -> 2 -> 5 since it would take too long.

Example 3:

Input: maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: -1
Explanation: There is no way to reach city 5 from city 0 within 25 minutes.

Constraints:

  • 1 <= maxTime <= 1000
  • n == passingFees.length
  • 2 <= n <= 1000
  • n - 1 <= edges.length <= 1000
  • 0 <= xi, yi <= n - 1
  • 1 <= timei <= 1000
  • 1 <= passingFees[j] <= 1000 
  • The graph may contain multiple edges between two nodes.
  • The graph does not contain self loops.

Approach overview

Problem Overview: You are given a graph where each city has a passing fee and each road has a travel time. Starting from city 0, reach city n-1 without exceeding maxTime. The goal is to minimize the total cost (sum of passing fees). If the destination cannot be reached within the allowed time, return -1.

This is a constrained shortest path problem. Traditional shortest path algorithms minimize either distance or cost, but here you must minimize cost while keeping total travel time ≤ maxTime. That constraint turns the problem into a hybrid of graph traversal and dynamic programming.

Approach 1: Dijkstra's Algorithm with Time Constraint (Time: O(E log V), Space: O(V * maxTime))

Treat each state as (city, timeSpent). Instead of tracking only the shortest distance, maintain the minimum cost required to reach a city at a specific time. Use a priority queue ordered by cost. From the current state, iterate over neighboring cities and push a new state if the updated time does not exceed maxTime. Maintain a DP table cost[city][time] to avoid revisiting worse states. This approach works because Dijkstra always expands the lowest-cost state first, ensuring that once the destination is reached within the allowed time, the cost is minimal. It performs well when the graph is sparse and is usually the fastest solution in practice.

Approach 2: Bellman-Ford Style Dynamic Programming (Time: O(maxTime * E), Space: O(V))

Another way is to iterate over time like a dynamic programming dimension. Maintain an array where dp[i] stores the minimum cost to reach city i. For each time unit up to maxTime, relax all edges. When relaxing an edge (u → v) with travel time t, update the cost for reaching v if the total time stays within the limit. To avoid overwriting values in the same iteration, copy the previous DP state before relaxing edges. This approach resembles the Bellman-Ford algorithm applied across time layers and works well for dense graphs. It explicitly explores all feasible transitions without using a priority queue.

Both solutions rely on modeling the graph using adjacency lists built from the input arrays. The key insight is that the same city can be visited multiple times if the arrival time differs, because a later arrival might still produce a cheaper total cost.

Recommended for interviews: Dijkstra with a time constraint is the preferred solution. Interviewers expect you to recognize this as a shortest-path problem with an additional state dimension. The Bellman-Ford style DP demonstrates strong understanding of relaxation techniques and constrained path problems, but the priority-queue solution is usually considered the optimal and most scalable approach.

Approach 1: Dijkstra's Algorithm with Time Constraint

This approach uses a variation of Dijkstra's algorithm to find the path with the minimum cost. While standard Dijkstra's algorithm optimizes for the shortest path, here, we will need to consider both the cost and the time constraints.

We will use a priority queue to focus on minimizing cost, and keep an array to track the minimum time to reach each city. If a city can be reached with a lesser cost within the allowed time, we choose that path. This approach involves maintaining additional state for the journey's time and cost.

import heapq

def min_cost_to_reach_city(max_time, edges, passing_fees):
    n = len(passing_fees)
    graph = [[] for _ in range(n)]
    for x, y, time in edges:
        graph[x].append((y, time))
        graph[y].append((x, time))

    pq = [(passing_fees[0], 0, 0)]  # (current_cost, current_time, current_city)
    min_cost = [float('inf')] * n
    min_time = [float('inf')] * n
    min_cost[0] = passing_fees[0]
    min_time[0] = 0

    while pq:
        cur_cost, cur_time, cur_city = heapq.heappop(pq)
        if cur_city == n - 1:
            return cur_cost

        for next_city, travel_time in graph[cur_city]:
            new_time = cur_time + travel_time
            new_cost = cur_cost + passing_fees[next_city]

            if new_time <= max_time and new_cost < min_cost[next_city]:
                min_cost[next_city] = new_cost
                min_time[next_city] = new_time
                heapq.heappush(pq, (new_cost, new_time, next_city))

    return -1

maxTime = 30
edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]]
passingFees = [5,1,2,20,20,3]
print(min_cost_to_reach_city(maxTime, edges, passingFees))
import java.util.*;

public class Solution {
    static class State {
        int time, cost, city;
        State(int time, int cost, int city) {
            this.time = time;
            this.cost = cost;
            this.city = city;
        }
    }

    public int minCostToReachCity(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        for (int[] edge : edges) {
            graph[edge[0]].add(new int[]{edge[1], edge[2]});
            graph[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        int[] minCost = new int[n];
        int[] minTime = new int[n];
        Arrays.fill(minCost, Integer.MAX_VALUE);
        Arrays.fill(minTime, Integer.MAX_VALUE);
        minCost[0] = passingFees[0];
        minTime[0] = 0;

        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.cost));
        pq.add(new State(0, passingFees[0], 0));

        while (!pq.isEmpty()) {
            State cur = pq.poll();
            if (cur.city == n - 1) return cur.cost;
            for (int[] next : graph[cur.city]) {
                int nextCity = next[0], travelTime = next[1];
                int newTime = cur.time + travelTime;
                int newCost = cur.cost + passingFees[nextCity];

                if (newTime <= maxTime && newCost < minCost[nextCity]) {
                    minCost[nextCity] = newCost;
                    minTime[nextCity] = newTime;
                    pq.add(new State(newTime, newCost, nextCity));
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int maxTime = 30;
        int[][] edges = {{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}};
        int[] passingFees = {5,1,2,20,20,3};
        System.out.println(sol.minCostToReachCity(maxTime, edges, passingFees));
    }
}
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, pair<int, int>> State;

int minCostToReachCity(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
    int n = passingFees.size();
    vector<vector<pair<int, int>>> graph(n);
    for(auto& edge : edges) {
        graph[edge[0]].emplace_back(edge[1], edge[2]);
        graph[edge[1]].emplace_back(edge[0], edge[2]);
    }

    vector<int> minCost(n, INT_MAX), minTime(n, INT_MAX);
    minCost[0] = passingFees[0];
    minTime[0] = 0;
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({passingFees[0], {0, 0}});

    while(!pq.empty()) {
        auto [curCost, p] = pq.top(); pq.pop();
        int curCity = p.first, curTime = p.second;
        if(curCity == n - 1) return curCost;

        for(auto &[nextCity, travelTime] : graph[curCity]) {
            int nextTime = curTime + travelTime;
            int nextCost = curCost + passingFees[nextCity];

            if(nextTime <= maxTime && nextCost < minCost[nextCity]) {
                minCost[nextCity] = nextCost;
                minTime[nextCity] = nextTime;
                pq.push({nextCost, {nextCity, nextTime}});
            }
        }
    }

    return -1;
}

int main() {
    int maxTime = 30;
    vector<vector<int>> edges = {{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}};
    vector<int> passingFees = {5,1,2,20,20,3};
    int result = minCostToReachCity(maxTime, edges, passingFees);
    cout << result << endl;
    return 0;
}
const minCostToReachCity = (maxTime, edges, passingFees) => {
    const n = passingFees.length;
    const graph = Array.from({ length: n }, () => []);
    for(const [u, v, time] of edges) {
        graph[u].push([v, time]);
        graph[v].push([u, time]);
    }

    const pq = [[passingFees[0], 0, 0]];  // [cost, time, city]
    const minCost = new Array(n).fill(Infinity);
    const minTime = new Array(n).fill(Infinity);
    minCost[0] = passingFees[0];
    minTime[0] = 0;

    while(pq.length) {
        // Sort by cost to use as priority queue
        pq.sort(([cost1], [cost2]) => cost1 - cost2);
        const [curCost, curTime, curCity] = pq.shift();
        if (curCity === n - 1) return curCost;

        for(const [nextCity, travelTime] of graph[curCity]) {
            const newTime = curTime + travelTime;
            const newCost = curCost + passingFees[nextCity];

            if (newTime <= maxTime && newCost < minCost[nextCity]) {
                minCost[nextCity] = newCost;
                minTime[nextCity] = newTime;
                pq.push([newCost, newTime, nextCity]);
            }
        }
    }

    return -1;
};

const maxTime = 30;
const edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]];
const passingFees = [5,1,2,20,20,3];
console.log(minCostToReachCity(maxTime, edges, passingFees));
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define INF INT_MAX
#include <stdbool.h>

typedef struct {
    int time, cost, city;
} State;

int cmp(const void *a, const void *b) {
    State *s1 = (State *)a;
    State *s2 = (State *)b;
    return s1->cost - s2->cost;
}

int minCostToReachCity(int maxTime, int n, int edges[][3], int edgesSize, int passingFees[]) {
    bool *done = malloc(sizeof(bool) * n);
    for (int i = 0; i < n; i++) done[i] = false;
    int *minTime = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) minTime[i] = INF;
    minTime[0] = 0;
    int *totalMinCost = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) totalMinCost[i] = INF;
    totalMinCost[0] = passingFees[0];
    State pq[n * n];
    unsigned int pqSize = 0;

    pq[pqSize++] = (State){0, passingFees[0], 0};

    while (pqSize > 0) {
        qsort(pq, pqSize, sizeof(pq[0]), cmp);
        State current = pq[--pqSize];

        if (done[current.city]) continue;
        done[current.city] = true;

        if (current.city == n - 1) {
            free(done); free(minTime); free(totalMinCost);
            return current.cost;
        }

        for (int i = 0; i < edgesSize; i++) {
            int nextCity = -1, nextTime = 0;
            if (edges[i][0] == current.city) {
                nextCity = edges[i][1];
                nextTime = edges[i][2];
            } else if (edges[i][1] == current.city) {
                nextCity = edges[i][0];
                nextTime = edges[i][2];
            }

            if (nextCity == -1 || done[nextCity]) continue;

            int newTime = current.time + nextTime;
            int newCost = current.cost + passingFees[nextCity];

            if (newTime <= maxTime && newCost < totalMinCost[nextCity]) {
                totalMinCost[nextCity] = newCost;
                minTime[nextCity] = newTime;
                pq[pqSize++] = (State){newTime, newCost, nextCity};
            }
        }
    }

    free(done); free(minTime); free(totalMinCost);
    return -1;
}

int main() {
    int maxTime = 30;
    int edges[][3] = {{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}};
    int passingFees[] = {5,1,2,20,20,3};
    int n = 6;
    int result = minCostToReachCity(maxTime, n, edges, 6, passingFees);
    printf("%d\n", result);
    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    class State : IComparable<State> {
        public int time, cost, city;
        public State(int time, int cost, int city) {
            this.time = time;
            this.cost = cost;
            this.city = city;
        }
        public int CompareTo(State other) {
            return this.cost.CompareTo(other.cost);
        }
    }

    public int MinCostToReachCity(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.Length;
        var graph = new List<int[]>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int[]>();
        foreach (var edge in edges) {
            graph[edge[0]].Add(new[] { edge[1], edge[2] });
            graph[edge[1]].Add(new[] { edge[0], edge[2] });
        }

        int[] minCost = new int[n];
        int[] minTime = new int[n];
        Array.Fill(minCost, int.MaxValue);
        Array.Fill(minTime, int.MaxValue);
        minCost[0] = passingFees[0];
        minTime[0] = 0;

        var pq = new SortedSet<State> { new State(0, passingFees[0], 0) };

        while (pq.Count > 0) {
            var cur = pq.Min;
            pq.Remove(cur);
            if (cur.city == n - 1) return cur.cost;
            foreach (var next in graph[cur.city]) {
                int nextCity = next[0], travelTime = next[1];
                int newTime = cur.time + travelTime;
                int newCost = cur.cost + passingFees[nextCity];

                if (newTime <= maxTime && newCost < minCost[nextCity]) {
                    minCost[nextCity] = newCost;
                    minTime[nextCity] = newTime;
                    pq.Add(new State(newTime, newCost, nextCity));
                }
            }
        }

        return -1;
    }

    public static void Main(string[] args) {
        var sol = new Solution();
        int maxTime = 30;
        int[][] edges = new[]{new[]{0,1,10},new[]{1,2,10},new[]{2,5,10},new[]{0,3,1},new[]{3,4,10},new[]{4,5,15}};
        int[] passingFees = {5,1,2,20,20,3};
        Console.WriteLine(sol.MinCostToReachCity(maxTime, edges, passingFees));
    }
}

The Python solution applies a priority queue (heap) for managing states during graph traversal. Lesser cost paths within the time limit enter the queue, facilitating exploration of feasible paths. The algorithm halts upon accessing the destination within a feasible path.

Complexity

Time Complexity: O(E log V), dictated principally by the queue operations over the edges.

Space Complexity: O(V + E), accountable for graph construction and state management during execution.

Try this approach in the editor

Approach 2: Bellman-Ford Algorithm with Time Cost

The Bellman-Ford algorithm is apt for graphs with cycles and works generally well especially when negative weights might be a consideration (not in this problem though). It checks all edges repeatedly to relax them and can accommodate additional constraints by modifying its relaxations - here, including time tracking for paths.

def min_cost_to_reach_city(max_time, edges, passing_fees):
    n = len(passing_fees)
    min_cost = [float('inf')] * n
    min_cost[0] = passing_fees[0]

    min_time = [float('inf')] * n
    min_time[0] = 0

    for _ in range(n-1):
        for u, v, time in edges:
            if min_time[u] + time <= max_time:
                min_cost[v] = min(min_cost[v], min_cost[u] + passing_fees[v])
                min_time[v] = min(min_time[v], min_time[u] + time)

    return -1 if min_cost[-1] == float('inf') else min_cost[-1]

maxTime = 30
edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]]
passingFees = [5,1,2,20,20,3]
print(min_cost_to_reach_city(maxTime, edges, passingFees))
import java.util.*;

public class Solution {
    public int minCostToReachCity(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        int[] minCost = new int[n];
        int[] minTime = new int[n];
        Arrays.fill(minCost, Integer.MAX_VALUE);
        Arrays.fill(minTime, Integer.MAX_VALUE);
        minCost[0] = passingFees[0];
        minTime[0] = 0;

        for (int i = 1; i < n; ++i) {
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], time = edge[2];
                if (minCost[u] != Integer.MAX_VALUE && minTime[u] + time <= maxTime) {
                    minCost[v] = Math.min(minCost[v], minCost[u] + passingFees[v]);
                    minTime[v] = Math.min(minTime[v], minTime[u] + time);
                }
            }
        }

        return minCost[n-1] == Integer.MAX_VALUE ? -1 : minCost[n-1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int maxTime = 30;
        int[][] edges = {{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}};
        int[] passingFees = {5,1,2,20,20,3};
        System.out.println(sol.minCostToReachCity(maxTime, edges, passingFees));
    }
}
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int minCostToReachCity(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
    int n = passingFees.size();
    vector<int> minCost(n, INT_MAX), minTime(n, INT_MAX);
    minCost[0] = passingFees[0];
    minTime[0] = 0;

    for (int i = 1; i < n; ++i) {
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], time = edge[2];
            if (minCost[u] != INT_MAX && minTime[u] + time <= maxTime) {
                minCost[v] = min(minCost[v], minCost[u] + passingFees[v]);
                minTime[v] = min(minTime[v], minTime[u] + time);
            }
        }
    }

    return minCost[n-1] == INT_MAX ? -1 : minCost[n-1];
}

int main() {
    int maxTime = 30;
    vector<vector<int>> edges = {{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}};
    vector<int> passingFees = {5,1,2,20,20,3};
    cout << minCostToReachCity(maxTime, edges, passingFees) << endl;
    return 0;
}
const minCostToReachCity = (maxTime, edges, passingFees) => {
    const n = passingFees.length;
    const minCost = new Array(n).fill(Infinity);
    const minTime = new Array(n).fill(Infinity);
    minCost[0] = passingFees[0];
    minTime[0] = 0;

    for (let i = 1; i < n; ++i) {
        for (const [u, v, time] of edges) {
            if (minTime[u] + time <= maxTime) {
                minCost[v] = Math.min(minCost[v], minCost[u] + passingFees[v]);
                minTime[v] = Math.min(minTime[v], minTime[u] + time);
            }
        }
    }

    return minCost[n - 1] === Infinity ? -1 : minCost[n - 1];
};

const maxTime = 30;
const edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]];
const passingFees = [5,1,2,20,20,3];
console.log(minCostToReachCity(maxTime, edges, passingFees));
#include <stdio.h>
#include <limits.h>

int minCostToReachCity(int maxTime, int n, int edges[][3], int edgesSize, int passingFees[]) {
    int minCost[n];
    for (int i = 0; i < n; ++i) minCost[i] = INT_MAX;
    minCost[0] = passingFees[0];

    int minTime[n];
    for (int i = 0; i < n; ++i) minTime[i] = INT_MAX;
    minTime[0] = 0;

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < edgesSize; ++j) {
            int u = edges[j][0], v = edges[j][1], time = edges[j][2];
            if (minCost[u] != INT_MAX && minTime[u] + time <= maxTime) {
                if (minCost[v] > minCost[u] + passingFees[v]) {
                    minCost[v] = minCost[u] + passingFees[v];
                    minTime[v] = minTime[u] + time;
                }
            }
        }
    }

    return minCost[n - 1] == INT_MAX ? -1 : minCost[n - 1];
}

int main() {
    int maxTime = 30;
    int edges[][3] = {{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}};
    int passingFees[] = {5,1,2,20,20,3};
    int n = 6;
    int result = minCostToReachCity(maxTime, n, edges, 6, passingFees);
    printf("%d\n", result);
    return 0;
}
using System;

public class Solution {
    public int MinCostToReachCity(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.Length;
        var minCost = new int[n];
        var minTime = new int[n];
        Array.Fill(minCost, int.MaxValue);
        Array.Fill(minTime, int.MaxValue);
        minCost[0] = passingFees[0];
        minTime[0] = 0;

        for (int i = 1; i < n; ++i) {
            foreach (var edge in edges) {
                int u = edge[0], v = edge[1], time = edge[2];
                if (minCost[u] != int.MaxValue && minTime[u] + time <= maxTime) {
                    minCost[v] = Math.Min(minCost[v], minCost[u] + passingFees[v]);
                    minTime[v] = Math.Min(minTime[v], minTime[u] + time);
                }
            }
        }

        return minCost[n-1] == int.MaxValue ? -1 : minCost[n-1];
    }

    public static void Main(string[] args) {
        var sol = new Solution();
        int maxTime = 30;
        int[][] edges = new[]{new[]{0,1,10}, new[]{1,2,10}, new[]{2,5,10}, new[]{0,3,1}, new[]{3,4,10}, new[]{4,5,15}};
        int[] passingFees = {5,1,2,20,20,3};
        Console.WriteLine(sol.MinCostToReachCity(maxTime, edges, passingFees));
    }
}

Illustrating Bellman-Ford extensions, the Python solution modifies relaxation logic relative to time constraints to ameliorate impacts on outcomes. Filling straightforward iterations, the solution strategizes iterative concise corrections to edge-constrained paths meticulously.

Complexity

Time Complexity: O(V * E), common to repeat over vertex-border edges until edge states converge upon expected patterns.

Space Complexity: O(V), deriving from moderate data structure caches managing path-related hope and history.

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j] to represent the minimum cost to reach city j from city 0 after i minutes. Initially, f[0][0] = passingFees[0], and the rest f[0][j] = +infty.

Next, within the time range [1, maxTime], we traverse all edges. For each edge (x, y, t), if t leq i, then we:

  • Can first spend i - t minutes to reach city y from city 0, then spend t minutes to reach city x from city y, and add the passing fee to reach city x, i.e., f[i][x] = min(f[i][x], f[i - t][y] + passingFees[x]);
  • Can also first spend i - t minutes to reach city x from city 0, then spend t minutes to reach city y from city x, and add the passing fee to reach city y, i.e., f[i][y] = min(f[i][y], f[i - t][x] + passingFees[y]).

The final answer is min{f[i][n - 1]}, where i \in [0, maxTime]. If the answer is +infty, return -1.

The time complexity is O(maxTime times (m + n)), where m and n are the number of edges and cities, respectively. The space complexity is O(maxTime times n).

function minCost(maxTime: number, edges: number[][], passingFees: number[]): number {
    const [m, n] = [maxTime, passingFees.length];
    const f: number[][] = Array.from({ length: m + 1 }, () => Array(n).fill(Infinity));
    f[0][0] = passingFees[0];
    for (let i = 1; i <= m; ++i) {
        for (const [x, y, t] of edges) {
            if (t <= i) {
                f[i][x] = Math.min(f[i][x], f[i - t][y] + passingFees[x]);
                f[i][y] = Math.min(f[i][y], f[i - t][x] + passingFees[y]);
            }
        }
    }
    let ans = Infinity;
    for (let i = 1; i <= m; ++i) {
        ans = Math.min(ans, f[i][n - 1]);
    }
    return ans === Infinity ? -1 : ans;
}
func minCost(maxTime int, edges [][]int, passingFees []int) int {
	m, n := maxTime, len(passingFees)
	f := make([][]int, m+1)
	const inf int = 1 << 30
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = passingFees[0]
	for i := 1; i <= m; i++ {
		for _, e := range edges {
			x, y, t := e[0], e[1], e[2]
			if t <= i {
				f[i][x] = min(f[i][x], f[i-t][y]+passingFees[x])
				f[i][y] = min(f[i][y], f[i-t][x]+passingFees[y])
			}
		}
	}
	ans := inf
	for i := 1; i <= m; i++ {
		ans = min(ans, f[i][n-1])
	}
	if ans == inf {
		return -1
	}
	return ans
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dijkstra's Algorithm with Time Constraint

Time Complexity: O(E log V), dictated principally by the queue operations over the edges.

Space Complexity: O(V + E), accountable for graph construction and state management during execution.

Bellman-Ford Algorithm with Time Cost

Time Complexity: O(V * E), common to repeat over vertex-border edges until edge states converge upon expected patterns.

Space Complexity: O(V), deriving from moderate data structure caches managing path-related hope and history.

Dynamic Programming–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dijkstra's Algorithm with Time ConstraintO(E log V)O(V * maxTime)Best general solution for sparse graphs and interview settings. Efficient with priority queue pruning.
Bellman-Ford Dynamic ProgrammingO(maxTime * E)O(V)Useful when modeling time as a DP dimension or when avoiding priority queues.

Frequently asked questions

Is Minimum Cost to Reach Destination in Time easy or hard?

Minimum Cost to Reach Destination in Time is classified as a Hard problem on LeetCode. The difficulty comes from combining graph shortest-path techniques with a time constraint and dynamic programming state management.

Minimum Cost to Reach Destination in Time Python/Java solution

Python and Java implementations typically use a priority queue (heapq in Python or PriorityQueue in Java) for the Dijkstra approach. The algorithm pushes states containing cost, node, and time, while pruning transitions that exceed the allowed time limit.

How to solve Minimum Cost to Reach Destination in Time in O(E log V)?

Build an adjacency list for the graph and run a modified Dijkstra algorithm. Store states as (cost, city, timeSpent) in a priority queue. Only push transitions where timeSpent + edgeTime ≤ maxTime, and track the best cost for each (city, time) state to avoid redundant work.

What is the best approach for Minimum Cost to Reach Destination in Time?

The most efficient approach uses Dijkstra's algorithm with an additional state for time. Each state represents (city, timeSpent), and a priority queue always expands the path with the lowest accumulated cost. This guarantees the cheapest route that also satisfies the maxTime constraint with a time complexity of O(E log V).

Is Minimum Cost to Reach Destination in Time asked at Google/Amazon/Meta?

This problem type frequently appears in interviews at companies like Amazon, Google, and Meta because it tests graph traversal with constraints. Candidates must combine shortest path algorithms with dynamic programming ideas, which is a common real-world optimization scenario.

What data structure is used in Minimum Cost to Reach Destination in Time?

Key data structures include an adjacency list for representing the graph, a priority queue (min-heap) for the Dijkstra approach, and dynamic programming arrays for tracking minimum cost per city and time. These structures allow efficient exploration of constrained paths.

What is the time complexity of Minimum Cost to Reach Destination in Time?

The optimal solution using Dijkstra's algorithm runs in O(E log V) time with a priority queue, while storing states for different arrival times. The alternative Bellman-Ford style dynamic programming approach runs in O(maxTime * E) time because every edge may be relaxed for each time step.

Comments

Next problem · similarMaximum Cost of Trip With K HighwaysHard
Now write it yourselfClose this page and solve Minimum Cost to Reach Destination in Time in the editor, without looking.
Practise Minimum Cost to Reach Destination in Time