Minimize Highway Travel Time with Optimal Rest‑Stop Charging (DP Solution)

Problem Description

A driver has an autonomous electric vehicle with a maximum range of 1000 km. The vehicle must travel from city A to city B, a distance D (0 ≤ D ≤ 1,000,000, D is a multiple of 100) kilometers away, staying on a highway where the speed is fixed at 100 km/h. Along the route there are N (0 ≤ N ≤ 10,000) rest stations, each providing charging service and reporting a real‑time queueing time (in hours). A charging session always lasts exactly 1 hour and fully recharges the battery. Queueing time does not consume battery. The vehicle may deplete its battery completely before recharging.

Input Format

First line: integer D.

Second line: integer N.

Next N lines: two integers per line – the distance of a rest station from city A and its queueing time (hours). The stations are given in increasing order of distance.

Output Format

Output the minimum total travel time (in hours) required to reach city B, including driving time, queueing time, and charging time.

Solution Overview

The driving time is deterministic: the vehicle travels at 100 km/h, so the total driving time equals D / 100 hours, regardless of where it stops to charge. The optimization problem therefore reduces to minimizing the total waiting time, i.e., the sum of queueing times plus the mandatory 1‑hour charging at each selected station.

We model the problem as a shortest‑path on a directed acyclic graph where each node corresponds to a location (start, each rest station, and destination). An edge from node j to node i is feasible if the distance between them does not exceed the vehicle's range (1000 km). Traversing such an edge means driving from j to i without any intermediate charge. The cost of arriving at node i and charging there is the queueing time at i plus the fixed 1‑hour charging time.

Dynamic Programming Formulation

Construct a list lst of length N+2 where each element is [distance, stop_time]. For the start node we use [0, 0], for each station we store [dist, queue+1], and for the destination we store [D, 0].

Define dp[i] as the minimum total waiting time (queue + charging) needed to reach node i and charge there. The start node has dp[0] = 0.

Transition: for each node i (1 ≤ i ≤ N+1) consider all previous nodes j (i‑1 … 0) such that lst[i][0] - lst[j][0] ≤ 1000. Then dp[i] = min(dp[i], dp[j] + lst[i][1]) If the distance exceeds 1000 km we break the inner loop because earlier nodes are even farther.

The answer is dp[N+1] + D // 100, where dp[N+1] is the minimal waiting time to reach the destination and D // 100 is the fixed driving time.

Algorithm (Python 3)

from math import inf

D = int(input())
N = int(input())

# list of [distance, total_stop_time]
lst = [[0, 0]]  # start point, no waiting
for _ in range(N):
    dist, queue = map(int, input().split())
    lst.append([dist, queue + 1])  # queue + 1 hour charging
lst.append([D, 0])  # destination, no charging needed

# dp[i] = minimal waiting time to reach node i and charge there
dp = [inf] * (N + 2)
dp[0] = 0

for i in range(1, N + 2):
    # look backwards; stop when distance > 1000 km
    for j in range(i - 1, -1, -1):
        if lst[i][0] - lst[j][0] > 1000:
            break
        dp[i] = min(dp[i], dp[j] + lst[i][1])

# total time = driving time + minimal waiting time
print(dp[-1] + D // 100)

Complexity Analysis

Time complexity: O(N) in practice because each inner loop iterates over at most the stations that lie within the last 1000 km, which is bounded by a small constant.

Space complexity: O(N) for the lst and dp arrays.