Formatted question description: https://leetcode.ca/all/1928.html

# 1928. Minimum Cost to Reach Destination in Time

## Level

Hard

## Description

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] = [x_i, y_i, time_i]`

denotes a road between cities `x_i`

and `y_i`

that takes `time_i`

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 <= x_i, y_i <= n - 1`

`1 <= time_i <= 1000`

`1 <= passingFees[j] <= 1000`

- The graph may contain multiple edges between two nodes.
- The graph does not contain self loops.

## Solution

First, use maps to store each city’s adjacent cities and corresponding times. Next, use dynamic programming to find the minimum cost. Create a 2D array `costs`

where `costs[i][j]`

is the minimum cost to reach `i`

at time `j`

, with `0 <= i < n`

and `0 <= j <= maxTime`

. Starting from city 0, find the minimum values of all elements in `costs`

. Finally, return the minimum value in `costs[n - 1]`

, or -1 if it is impossible to reach city `n - 1`

within `maxTime`

.

```
class Solution {
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
int n = passingFees.length;
int[][] times = new int[n][n];
for (int i = 0; i < n; i++)
Arrays.fill(times[i], Integer.MAX_VALUE);
for (int[] edge : edges) {
int x = edge[0], y = edge[1], time = edge[2];
if (x > y) {
int temp = x;
x = y;
y = temp;
}
if (time <= maxTime && time < times[x][y]) {
times[x][y] = time;
times[y][x] = time;
}
}
Map<Integer, Integer>[] map = new Map[n];
for (int i = 0; i < n; i++)
map[i] = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (times[i][j] != Integer.MAX_VALUE) {
map[i].put(j, times[i][j]);
map[j].put(i, times[i][j]);
}
}
}
int[][] costs = new int[n][maxTime + 1];
for (int i = 0; i < n; i++)
Arrays.fill(costs[i], Integer.MAX_VALUE);
costs[0][0] = passingFees[0];
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] indexTimeCost1, int[] indexTimeCost2) {
if (indexTimeCost1[2] != indexTimeCost2[2])
return indexTimeCost1[2] - indexTimeCost2[2];
else
return indexTimeCost1[1] - indexTimeCost2[1];
}
});
priorityQueue.offer(new int[]{0, 0, passingFees[0]});
while (!priorityQueue.isEmpty()) {
int[] indexTimeCost = priorityQueue.poll();
int index = indexTimeCost[0], time = indexTimeCost[1], cost = indexTimeCost[2];
Map<Integer, Integer> nextMap = map[index];
for (Map.Entry<Integer, Integer> entry : nextMap.entrySet()) {
int nextIndex = entry.getKey(), nextTime = entry.getValue();
int totalTime = time + nextTime;
if (totalTime <= maxTime) {
int totalCost = cost + passingFees[nextIndex];
if (totalCost < costs[nextIndex][totalTime]) {
costs[nextIndex][totalTime] = totalCost;
priorityQueue.offer(new int[]{nextIndex, totalTime, totalCost});
}
}
}
}
int minCost = Integer.MAX_VALUE;
for (int i = 0; i <= maxTime; i++)
minCost = Math.min(minCost, costs[n - 1][i]);
return minCost == Integer.MAX_VALUE ? -1 : minCost;
}
}
```