Use uniform-cost search to find the lowest-cost route on a road map.
What to build
A program that finds the cheapest route between two towns.
Requirements
- Roads go both ways and have positive costs. If several routes have the same lowest cost, print the one that comes first when the routes are compared town by town in alphabetical order.
- Print the route as
A -> B -> Cand thencost N, or printno route.
Input
Line 1: r. Then r lines TOWN TOWN COST. Last line: the start and the goal.
Output
Two lines, or no route.
Constraints
r ≤ 200; town names have no spaces.
Example
Input:
5
A B 4
A C 1
C B 2
B D 5
C D 8
A D
Output:
A -> C -> B -> D
cost 8
Why it works
Uniform-cost search takes routes out of the frontier in order of cost, so the goal comes out first along a cheapest route.
Examples
Example 1 · Input
5 A B 4 A C 1 C B 2 B D 5 C D 8 A D
Expected output
A -> C -> B -> D cost 8
Example 2 · Input
2 A B 1 C D 1 A D
Expected output
no route
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Use a priority queue of (cost, path); the first time the goal is taken out, its path is the cheapest.
Hint 2
Storing the whole path as a list makes ties come out in alphabetical order automatically.
Solution
Show one correct solution (try it yourself first)
import heapq
roads = {}
for _ in range(int(input())):
a, b, cost = input().split()
roads.setdefault(a, {})[b] = int(cost)
roads.setdefault(b, {})[a] = int(cost)
start, goal = input().split()
frontier, done, answer = [(0, [start])], set(), None
while frontier:
cost, path = heapq.heappop(frontier)
town = path[-1]
if town in done:
continue
done.add(town)
if town == goal:
answer = (cost, path)
break
for nxt, step in roads.get(town, {}).items():
if nxt not in done:
heapq.heappush(frontier, (cost + step, path + [nxt]))
if answer:
print(" -> ".join(answer[1]))
print("cost", answer[0])
else:
print("no route")