Solve Shortest Paths and Rental Allocation

You are given two independent coding problems. ## Problem 1: Shortest path in a weighted graph You are given a weighted graph where each edge has a non-negative distance. Given a start node `source` and a target node `target`: 1. Determine whether `target` is reachable from `source`. 2. If it is reachable, return the shortest distance from `source` to `target`. 3. Follow-up: suppose the path must pass through a required intermediate node `mid`. Determine whether such a path exists and, if it exists, return the minimum total distance from `source` to `target` while visiting `mid`. Clarify whether the graph is directed or undirected, and handle either case according to the input representation. ## Problem 2: Assign car rental requests to the minimum number of cars You are given a list of car rental requests. Each request has: - `pickup_time` - `return_time` You are also given a `Car` class with fields similar to: ```python class Car: def __init__(self, id): self.id = id self.rental_record = [] ``` Implement the following: 1. Return the minimum number of cars required to satisfy all rental requests, assuming one car cannot serve overlapping requests. 2. Follow-up: actually assign requests to cars. For each `Car` instance, record the requests assigned to that car in `car.rental_record`. A car can be reused if its previous request has already ended before the next request starts. State clearly whether `return_time == pickup_time` counts as non-overlapping.