جواب «Route Planner» چالش 8 از جلسهی 35
سؤال
ورودی: جادههای دوطرفه بین شهرها <a> <b> تا end، سپس یک خط <from> <to>. با BFS (همسایهها به ترتیب الفبایی) و دیکشنری parent کوتاهترین مسیر (کمترین تعداد جاده) را بازسازی و به شکل A -> B -> C چاپ کنید و سپس stops: <تعداد جادهها>. اگر مسیری نبود فقط no route.
راهنما
parent[start] = None؛ پس از BFS از مقصد با parent به عقب بروید و لیست را برعکس کنید.
یک جواب درست
from collections import defaultdict, deque
graph = defaultdict(list)
while True:
line = input()
if line == "end":
break
a, b = line.split()
graph[a].append(b)
graph[b].append(a)
src, dst = input().split()
parent = {src: None}
queue = deque([src])
while queue:
node = queue.popleft()
if node == dst:
break
for nxt in sorted(graph[node]):
if nxt not in parent:
parent[nxt] = node
queue.append(nxt)
if dst not in parent:
print("no route")
else:
path = []
node = dst
while node is not None:
path.append(node)
node = parent[node]
path.reverse()
print(" -> ".join(path))
print(f"stops: {len(path) - 1}")
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن