真题精讲：射箭计分与最短路计数

# 真题精讲：两道八级真题风格编程题一次讲透

# —— 题 1：射箭计分（几何判定，对应题库 py-exam-l8-a1）——
def archery(a, b, r, points):
    total = 0
    r2 = r * r
    for x, y in points:
        d2 = (x - a) ** 2 + (y - b) ** 2   # 关键技巧：比较距离的平方，不开根号
        if d2 < r2:
            total += 10                    # 圆内（不含边界）10 分
        elif d2 == r2:
            total += 5                     # 恰好压线 5 分
    return total

# 样例：圆心 (0, 0)，半径 5，共 5 支箭
pts = [(3, 4), (5, 0), (6, 0), (0, 0), (-3, -4)]
print("射箭总得分:", archery(0, 0, 5, pts))   # 5+5+0+10+5

# —— 题 2：最短上学路线有几条（Dijkstra + 计数，对应题库 py-exam-l8-a2）——
import heapq

def count_shortest(n, edges, start, end):
    MOD = 10**9 + 7
    graph = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    INF = float("inf")
    dist = [INF] * (n + 1)
    cnt = [0] * (n + 1)
    dist[start] = 0
    cnt[start] = 1
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:               # 更短：距离与方案数一起更新
                dist[v] = nd
                cnt[v] = cnt[u]
                heapq.heappush(heap, (nd, v))
            elif nd == dist[v]:            # 一样短：方案数累加并取模
                cnt[v] = (cnt[v] + cnt[u]) % MOD
    return dist[end], cnt[end]

# 样例：4 个路口、4 条双向路，1→2→4 与 1→3→4 并列最短
edges = [(1, 2, 2), (1, 3, 2), (2, 4, 3), (3, 4, 3)]
d, c = count_shortest(4, edges, 1, 4)
print("最短路程:", d, "路线条数:", c)