综合项目：校园导航小助手

# 综合项目：校园导航小助手
# 三层架构：数据层（地图）→ 算法层（最短路）→ 交互层（查询）
import heapq

# ---------- 数据层：校园地图 ----------
places = ["校门", "图书馆", "教学楼", "实验楼", "体育馆", "食堂"]
roads = [  # (地点A, 地点B, 步行分钟)
    ("校门", "图书馆", 3),
    ("校门", "教学楼", 5),
    ("图书馆", "实验楼", 4),
    ("教学楼", "实验楼", 2),
    ("教学楼", "食堂", 4),
    ("实验楼", "体育馆", 3),
    ("食堂", "体育馆", 2),
]

# ---------- 算法层：Dijkstra + 路径还原 ----------
def shortest_path(start, end):
    graph = {name: [] for name in places}
    for a, b, w in roads:
        graph[a].append((b, w))
        graph[b].append((a, w))
    dist = {start: 0}
    pre = {}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue
        if u == end:
            break                    # 终点出堆，最短路已确定
        for v, w in graph[u]:
            nd = d + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                pre[v] = u
                heapq.heappush(heap, (nd, v))
    if end not in dist:
        return None, []
    path = [end]
    while path[-1] != start:
        path.append(pre[path[-1]])
    path.reverse()
    return dist[end], path

# ---------- 交互层：来两趟查询 ----------
for s, e in [("校门", "体育馆"), ("图书馆", "食堂")]:
    d, path = shortest_path(s, e)
    print(s, "→", e, "最少步行", d, "分钟")
    print("  路线:", " → ".join(path))