Cheapest Route Within a Travel Deadline
Company: PhonePe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
The connected undirected road network has cities `0` through `n-1`. Each road `[u,v,time]` takes the stated number of minutes, and parallel roads are allowed. Every visit to a city incurs its `passingFees` entry, including the initial city and the destination. Starting at city 0, return the smallest total fee for reaching city `n-1` in at most `maxTime` minutes, or return `-1` if the deadline cannot be met.
```cpp
class Solution {
public:
int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees);
};
```
### Examples
**Example 1:**
```text
maxTime = 4, edges = [[0,1,2],[1,2,2],[0,2,5]], passingFees = [2,3,4]
Output: 9
Explanation: Only 0->1->2 arrives within four minutes.
```
**Example 2:**
```text
maxTime = 2, edges = [[0,1,2],[1,2,2]], passingFees = [1,2,3]
Output: -1
Explanation: Reaching city 2 needs four minutes.
```
### Constraints
- `1 <= maxTime <= 1000`; `2 <= n == passingFees.length <= 1000`.
- `n-1 <= edges.length <= 1000`.
- Endpoints are in `[0,n-1]`; road times and fees are in `[1,1000]`.
- Parallel edges are allowed; self-loops are absent.
### Clarifying Questions
Fees are paid on every visit, not just once per distinct city. The deadline is inclusive.
```hint Inspect the structure
Can the cheapest arrival at a city alone summarize all routes with different remaining time?
```
### Reasoning checkpoints
- Minimize the total fee among journeys meeting the inclusive deadline, while accounting for all city visits.
- Explain why a cheaper but slower arrival and a costlier but faster arrival may lead to different feasible continuations.
### Optional extensions
Can you save memory by discarding arrivals that cannot improve any feasible continuation?
Overview: Cheapest Route Within a Travel Deadline. Travel from city 0 to city n-1 through undirected roads [u,v,time]. Every visit to a city costs its passingFees entry, including the starting and destination cities. Roads may be parallel but never self-loops. Return the minimum total fee among journeys taking at most maxTime minutes, or -1 if none exists. The source describes the city network as connected.