Bellman-Ford算法检测负权环单测试用例不通过错误排查

任务：给定包含n个顶点、m条边的有向图，边权可能为负值，检测该图中是否存在负权环。

输入格式：以标准格式输入图结构。
约束条件：1 ≤ n ≤ 10³，0 ≤ m ≤ 10⁴，边权为绝对值不超过10³的整数。

输出格式：若图中存在负权环输出1，否则输出0。

import sys


def negative_cycle(adj, cost):
    #write your code here
    distance = [float('inf')] * len(adj)
    distance[0] = 0
    
    edges = []
    for i in range(len(adj)):
        for j in adj[i]:
            edges.append([i,j])
            
    for _ in range(len(adj)-1):
        for i in edges:
            a = i[0]
            b = adj[a].index(i[1])
            if distance[i[1]] > distance[a] + cost[a][b] and distance[a] != float('inf'):
                distance[i[1]] = distance[a] + cost[a][b]
                
    for i in edges:
        a, b = i[0], adj[i[0]].index(i[1])
        if distance[i[1]] > distance[a] + cost[a][b] and distance[a] != float('inf'):
            return 1
    return 0



if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(zip(data[0:(3 * m):3], data[1:(3 * m):3]), data[2:(3 * m):3]))
    data = data[3 * m:]
    adj = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]
    for ((a, b), w) in edges:
        adj[a - 1].append(b - 1)
        cost[a - 1].append(w)
    print(negative_cycle(adj, cost))

该代码可通过大部分测试用例，但存在1个测试用例运行失败：
失败用例：第12/19个测试用例，返回结果错误（运行耗时：0.23/10.00秒，内存占用：14229504/2147483648字节）

输入格式说明：
第一行输入顶点数、边数
后续每行依次输入边的起点顶点、终点顶点、边权值
逐行输入覆盖所有边

代码存在两处问题，其中第一处是导致测试用例失败的核心原因：

• 无法检测与0号顶点不连通的负权环
  现有代码初始化距离数组时，仅将0号顶点的距离设为0，Bellman-Ford算法执行过程中只会松弛从0号顶点出发可达的节点。如果负权环存在于和0号顶点完全不连通的其他连通分量中，这些分量内节点的初始距离始终为无穷大，松弛逻辑不会处理对应边，自然无法检测到该位置的负环，最终错误返回0。
  检测全图负权环的标准初始化方式是将所有顶点的初始距离都设为0，等价于虚拟一个向所有顶点连0权边的超级源点，保证所有连通分量的边都会参与松弛计算，不会漏掉任何位置的负环。
• 边权取值逻辑有bug，且存在性能浪费
  代码构建边列表时仅存储了边的起点和终点，每次松弛时都调用adj[a].index(i[1])查找边在邻接表中的索引来获取权值：
  • 如果同一个起点存在多条指向同一终点的平行边，index()只会返回第一个匹配项的索引，会导致后续平行边取错权值，直接造成计算结果错误。
  • list.index()是线性扫描操作，时间复杂度和对应顶点的出度正相关，在万级边的规模下会产生大量无意义的扫描操作，数据规模更大时很容易触发超时。
    更合理的做法是构建边列表时直接把边权一起存入，每条边保存为(起点, 终点, 权值)的三元组，松弛时直接读取权值即可，既不会出现取值错误，性能也更高。

内容的提问来源于stack exchange，提问作者Young42