بتل کد Battle Codeدارد باز می‌شود…

جواب «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}")

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن