Solve Shortest Paths and Rental Allocation

Problem Statement

You manage a fleet of rental cars across a city represented as a weighted graph where edges represent travel time between stations. You have a list of requests, where each request is defined as (start_station, end_station, start_time, duration).

Before a rental can be fulfilled, a car must travel from its current location to the start_station of the new request. If the car arrives at start_time or earlier, it waits until the request begins. The total time for a car to fulfill a request is travel_time(current_location, start_station) + duration.

Your tasks:

1. Implement a function to find the shortest travel time between any two stations in the graph.
2. Given a list of requests, determine the minimum number of cars required to fulfill all requests such that no request is missed.

Function Signature

def min_cars_required(graph, requests):
    # graph: list of (u, v, weight)
    # requests: list of (start_station, end_station, start_time, duration)
    pass

Constraints

• Number of stations N <= 500
• Number of requests M <= 10,000
• Graph edges have non-negative weights.

Example

• Stations: 3, Edges: [(0, 1, 5), (1, 2, 10)]
• Request 1: (0, 1, 10, 20)
• Request 2: (1, 2, 20, 10)
• If a car starts at 0, it can fulfill Req 1, then travel from 1 to 1 (time 0) to start Req 2.
• Result: 1 car is sufficient.

Edge Cases

• Disconnected graph (cannot reach station).
• Requests with overlapping start times.
• Car arrives exactly at the start time.