最短路：Dijkstra 与分层状态

import sys
import heapq

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
ids = {}                                   # 客户编号 → 1..n（快递站是 0）
adj = [[] for _ in range(n + 1)]
pos = 2
for i in range(1, n + 1):
    cid, d = int(data[pos]), int(data[pos + 1])
    pos += 2
    ids[cid] = i
    adj[0].append((i, d))                  # 快递站 ↔ 客户，双向
    adj[i].append((0, d))
for _ in range(m):
    a, b, d = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
    pos += 3
    i, j = ids[a], ids[b]
    adj[i].append((j, d))                  # 客户 ↔ 客户，双向
    adj[j].append((i, d))

def dijkstra(src):                         # 从 src 到每个关键点的最短距离
    dist = [float("inf")] * (n + 1)
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                       # 过期条目
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return dist

table = [dijkstra(s) for s in range(n + 1)]   # (n+1)×(n+1) 距离表：任意两个关键点之间的最短路

best = float("inf")
used = [False] * (n + 1)

def go(cur, count, total):                 # 在小表上回溯枚举送货顺序
    global best
    if total >= best:
        return
    if count == n:                         # 送完所有客户 → 回快递站
        best = min(best, total + table[cur][0])
        return
    for nxt in range(1, n + 1):
        if not used[nxt]:
            used[nxt] = True
            go(nxt, count + 1, total + table[cur][nxt])
            used[nxt] = False

go(0, 0, 0)
print(best if best != float("inf") else -1)

自测建议：题面两组示例（2500 / 9200）、第 10 节「客户 3 只能经站」的例子（10210）、单个客户往返（1 0 / 7 500 → 1000）。

import sys
import heapq

data = sys.stdin.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
proc = [0] + [int(x) for x in data[3:3 + n]]          # 算子处理时延，编号 1..n
adj = [[] for _ in range(n + 1)]
pos = 3 + n
for _ in range(m):
    u, v, t = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
    pos += 3
    adj[u].append((v, t))                              # 有向通道 u → v，传输时延 t

INF = float("inf")
dist = [[INF] * (k + 1) for _ in range(n + 1)]       # dist[节点][已用加速次数]
dist[1][0] = proc[1]                                   # 起点的处理时延也计入
heap = [(proc[1], 1, 0)]
while heap:
    d, u, used = heapq.heappop(heap)
    if d > dist[u][used]:                              # 过期条目
        continue
    for v, t in adj[u]:
        nd = d + t + proc[v]                           # 不加速：层内走
        if nd < dist[v][used]:
            dist[v][used] = nd
            heapq.heappush(heap, (nd, v, used))
        if used < k:                                   # 加速：跨到下一层，时延减半向下取整
            nd2 = d + t // 2 + proc[v]
            if nd2 < dist[v][used + 1]:
                dist[v][used + 1] = nd2
                heapq.heappush(heap, (nd2, v, used + 1))
best = min(dist[n])                                    # 终点的所有层里取最小（加速可以不用完）
print(-1 if best == INF else best)

自测建议：题面示例（k=0 → 24、k=1 → 20）、k=2 → 17、不可达（3 1 2 / 1 1 1 / 2 3 5 → -1）、加速用不满（2 1 3 / 1 1 / 1 2 4 → 4）；再自拟含重边、自环的输入。

import sys
from collections import deque

rows = [line.split() for line in sys.stdin.read().split("\n") if line.strip()]
n = len(rows)
matrix = [[int(x) for x in row] for row in rows]

seen = [False] * n
groups = 0
for start in range(n):
    if seen[start]:
        continue
    groups += 1                            # 一个新的连通分量：广播一台
    seen[start] = True
    q = deque([start])
    while q:
        u = q.popleft()
        for v in range(n):                 # 邻接矩阵：扫一行找直接相连的服务器
            if matrix[u][v] == 1 and not seen[v]:
                seen[v] = True
                q.append(v)
print(groups)

自测建议：第 08 节手算例（2）、全 1 矩阵（1）、单位矩阵（N）。行数由输入行数决定，不必先读 N。

import heapq

def dijkstra(n, adj, src):
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                   # 过期条目：堆里记的距离比表里的大 → 跳过
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:              # 松弛：更短就更新并压回堆
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

# 手推过的 3 节点：0→1 权 4，0→2 权 1，2→1 权 2
adj = [[(1, 4), (2, 1)], [], [(1, 2)]]
assert dijkstra(3, adj, 0) == [0, 3, 1]   # 0→2→1 = 3，不是直连的 4
assert dijkstra(2, [[], []], 0)[1] == float("inf")   # 不可达
assert dijkstra(1, [[]], 0) == [0]                   # 单点
adj2 = [[(1, 1), (2, 5)], [(2, 1)], [(3, 1)], []]
assert dijkstra(4, adj2, 0) == [0, 1, 2, 3]          # 绕行 0→1→2 = 2 优于直连 5

四条断言覆盖：绕行更短、不可达、单点、练习 1。删掉 if d > dist[u]: continue 结果仍对但会重复松弛。