Loading page…
Practice problem · easy
A parcel-delivery app sends a truck with fragile goods through a region of towns. Town i has a risk score risk[i] for damage, built from rough roads and road works, and a road joins two towns and can be driven both ways.
You work on the route planner. A route's risk is the sum of the risk scores of every town on it, including the town where the trip starts and the town where it ends. The app shows the trip with the least total risk, or says that there is no route.
Write least_risk(risk, roads, start, target).
risk[i] is the risk score of town i. The number of towns is len(risk).roads[i] = [a, b] is a road between two different towns. Roads can be listed more than once.start is the town where the trip begins and target is where it ends.start to target, counting every town on the route once for each visit, including both ends. Return -1 when target cannot be reached.Input: risk = [2, 5, 1, 3], roads = [[0, 1], [0, 2], [1, 3], [2, 3]], start = 0, target = 3
Output: 6Dijkstra starts with the start town's own risk. Entering a town adds that town's risk.
| Taken from the heap | Towns relaxed | Heap after |
|---|---|---|
| (2, town 0) | town 1 gives 7, town 2 gives 3 | (3, 2), (7, 1) |
| (3, town 2) | town 0 gives 5 (not better), town 3 gives 6 | (6, 3), (7, 1) |
| (6, town 3) | the target: stop |
The route 0, 2, 3 totals 2 + 1 + 3 = 6. The route 0, 1, 3 would total 2 + 5 + 3 = 10.
Input: risk = [1, 1, 1], roads = [[0, 1]], start = 0, target = 2
Output: -1No road reaches town 2.
Input: risk = [7], roads = [], start = 0, target = 0
Output: 7The trip starts and ends in the same town, whose own risk is counted once.
1 ≤ len(risk) ≤ 100,000, and 0 ≤ risk[i] ≤ 1,0000 ≤ len(roads) ≤ 100,000, and every road is [a, b] with 0 ≤ a, b < len(risk) and a ≠ b0 ≤ start, target < len(risk)There can be 100,000 towns and 100,000 roads, which is 200,000 directed edges. Dijkstra relaxes each once, so about 200,000 × 17 steps. Going over every road again and again until nothing improves can take one pass per town on a long chain, which is billions of steps.
least_risk · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.