Microsoft 每点最短回路：带权图从自身出发再返回

题目重点：对每个起点求返回自己的最小正权闭环；以从起点到某个入邻的最短路加最后一条回边求解。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练图有向，边权严格正，可有自环和重边；一个回路至少走一条边。
每个顶点输出最短返回代价，若没有任何正长度回路返回 0；正权确保 0 不与合法代价混淆。
如果原题是无向图，往返同一条边是否算环必须单独确认；本训练版不套用无向简单环算法。

解题路线

固定起点 s，任一返回 s 的回路最后必经入边 u→s；前半段从 s 到 u 的最小代价是 dist_s[u]，因此候选为 dist_s[u]+w(u,s)。
正权有向图从 s 运行 Dijkstra 求 dist_s，再扫描 s 的所有入边取最小候选；若没有可达入邻则记 0。
对所有 s 重复，得到每点答案。自环 s→s 直接形成 w 的候选，因为 dist_s[s]=0；多个回路会由最短路加最后入边覆盖。
若权重可能负，Dijkstra 失效且负环可能令最小回路代价无下界；若输出所有点的短环且 n 很小，可用 Floyd-Warshall 后扫描入边。

手动走一遍

0→1 权 2、1→2 权 3、2→0 权 4，三点各自最短回路成本都是 9。若另有 0→0 权 7，则 0 的最短回路为 7，1/2 仍为 9。孤立点无回路返回 0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Minimum positive-weight directed cycle returning to each vertex; 0 if absent."""

import heapq


def shortest_return_cycles(n: int, edges: list[tuple[int, int, int]]) -> list[int]:
    if n < 0:
        raise ValueError("negative vertex count")
    graph = [[] for _ in range(n)]
    incoming = [[] for _ in range(n)]
    for source, target, weight in edges:
        if not 0 <= source < n or not 0 <= target < n or weight <= 0:
            raise ValueError("vertices in range and positive weights required")
        graph[source].append((target, weight))
        incoming[target].append((source, weight))

    answers = []
    for start in range(n):
        distance = [float("inf")] * n
        distance[start] = 0
        heap = [(0, start)]
        while heap:
            cost, node = heapq.heappop(heap)
            if cost != distance[node]:
                continue
            for neighbor, weight in graph[node]:
                candidate = cost + weight
                if candidate < distance[neighbor]:
                    distance[neighbor] = candidate
                    heapq.heappush(heap, (candidate, neighbor))
        answer = min((distance[previous] + weight for previous, weight in incoming[start]), default=float("inf"))
        answers.append(0 if answer == float("inf") else int(answer))
    return answers

复杂度

n 点 m 边，逐起点二叉堆 Dijkstra，允许重边且堆中旧候选保留时上界 O(n(n+m) log(n+m)) 时间；邻接与入边 O(n+m) 空间，单次距离/堆 O(n+m)。小 n 可考虑 Floyd-Warshall O(n³) 时间、O(n²) 空间。

易错点与追问

容易失分的边界

dist(s,s)=0 就直接当最短回路，漏了至少一条边。
没有定义有向/无向及反向走同边是否允许。
负权边还用 Dijkstra。
无回路时输出 Infinity 而题目要求 0。
把所有顶点共享一条最短环的代价，忽略各点可达的环不同。

继续深挖

无向图若禁止同一条边往返，怎样找每点最短简单环？
图有负边但无负环时怎样做？
只需单个给定顶点答案时如何避免全源计算？
回路要求不重复顶点时正权最短解是否自动满足？