Hackerrank 测试用例不正确？ Dijkstra 最短距离 2

Question

Hackerrank - Dijkstra 最短距离 2

我被困在测试用例 7（我唯一失败的一个），我认为这是我的错。我下载了测试用例并检查了我生成的输出。

我做了 git 差异，但我看不出它们之间有任何区别。你能帮我验证我的代码发生了什么吗？

或者如果我的代码中没有问题，我想更改问题：

HackerRank Platform是不是经常出bug？

我在为求职面试做 HackerRank 挑战赛时经常遇到一个不明显的失败（通常是 13 个测试用例中的最后一两个），因此多次失败。不知道大家有没有类似的经历。我怀疑当我和朋友一起检查我提交的代码时，我们找不到任何边缘情况或错误。它应该是完美的。作为一直在 LeetCode 编码的程序员，这让我感到害怕，我开始在 HackerRank 上训练。

请指教。谢谢

资源：

Hackerrank 问题：https://www.hackerrank.com/challenges/dijkstrashortreach/problem
TestCase7 的输入和输出：https://drive.google.com/drive/u/0/folders/13Qa0k1mIZ5hVW32bRQa15_s8rH7f0-v4

P.S 在 google 驱动器文件夹中，我附上了我的输出：output_me.txt 和真实输出：output.txt。我确实为两个输出添加了新行（最初，所有答案都在一长行中，添加了新行以使其更易于阅读。）

代码：

import os
from collections import defaultdict
from heapq import heappop, heappush

MAX_INT = 2**31


# Build Graph
def buildGraph(edges):
    graph = defaultdict(list)
    trackMinEdge = {}

    # build min edges from u - v (adjacent)
    # for handling duplicate edges
    for u, v, weight in edges:
        u, v = min(u, v), max(u, v)
        if (u, v) in trackMinEdge:
            minWeight = trackMinEdge[(u, v)]
            if minWeight <= weight:
                # do not update
                continue
        # only update if (u, v) not in trackMinWeight
        # or the new weight is smaller than minWeight
        trackMinEdge[(u, v)] = weight

    # build graph from minimum adjancent edge
    for u, v in trackMinEdge:
        weight = trackMinEdge[(u, v)]
        graph[u].append((weight, v))
        graph[v].append((weight, u))

    return graph

# DJIKSTRA
def djikstra(n, graph, src, dest=None):
    dists = {}

    # setups
    seen = set()
    queue = [(0, src)]
    dists[src] = 0
    while queue:
        dist_u, u = heappop(queue)
        if u in seen: continue

        seen.add(u)
        for weight, v in graph.get(u, []):
            if v in seen: continue

            alt = dists[u] + weight
            if alt < dists.get(v, MAX_INT):
                dists[v] = alt
                heappush(queue, (alt, v))

    return dists


# Complete the shortestReach function below.
def shortestReach(n, edges, src):
    graph = buildGraph(edges)

    # edge cases: src not connected to any node
    if not (src in graph):
        return [-1 for _ in range(n-1)] 

    dists = djikstra(n, graph, src)

    distsTable = []
    for i in range(1, n+1):
        if i in dists and i != src:
            distsTable.append(dists[i])
        elif not (i in dists):
            distsTable.append(-1)

    return distsTable


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w+')

    t = int(input())

    for t_itr in range(t):
        nm = input().split()

        n = int(nm[0])

        m = int(nm[1])

        edges = []

        for _ in range(m):
            edges.append(list(map(int, input().rstrip().split())))

        s = int(input())

        result = shortestReach(n, edges, s)

        fptr.write(' '.join(map(str, result)))
        fptr.write('\n')

    fptr.close()

此致，

我

Answer 1

我试过你的代码，它实际上对 PyCharm 上的 Test Case#7 有效 - 实际输出与一个在预期的输出中。然而，由于 运行时错误 ，相同的代码在 Hackerrank 上失败。为什么会发生？

根据Hackerrank FAQ

Runtime error/Segmentation Fault. Your code terminated unexpectedly. Did you overrun your array? Is your code trying to divide by zero?

显然，这不是因为我们将某些东西除以 0 因为它在本地有效。还有什么？根据 Python 的 Hackerrank Environment，解决方案的内存限制为 512 Mb。

因此，我决定使用 tracemalloc 模块测量您的解决方案的内存使用情况。

import tracemalloc
tracemalloc.start()
...
# <solution code here>
...
print("Current usage: %d, Peak usage: %d" % tracemalloc.get_traced_memory())

输出

Current usage: 549627153, Peak usage: 550966939

如您所见，它实际上超过了 512 Mb 的限制，这就是为什么您可以拥有这个 Runtime Error。因此，请尝试降低解决方案的 space 复杂性。

我还注意到另一个问题 - 如果您使用 time 模块测量时间复杂度，那么 Test Case#7[=59= 需要超过 40 秒] 去完成。因此，如果您先解决 space 复杂性问题，这可能是您的下一个问题。

最后，不，Hackerrank 上没有错误 - 我的 Python 解决方案已通过所有测试。

更新

正如@Daniel（问题的作者）所问，我提供了我的优化版本的解决方案，它通过了 Hackerrank.
上的所有测试
# Complete the shortestReach function below. def shortestReach(n, distanceMatrix, s): queue = list() queue.append(s) minDistances = [-1] * (n + 1) minDistances[s] = 0 while queue: currentNode = queue.pop(0) for neighbor in distanceMatrix[currentNode]: newDistance = minDistances[currentNode] + distanceMatrix[currentNode][neighbor] prevDistance = minDistances[neighbor] if minDistances[neighbor] == -1: minDistances[neighbor] = newDistance else: minDistances[neighbor] = min(newDistance, minDistances[neighbor]) if prevDistance != minDistances[neighbor]: queue.append(neighbor) del minDistances[s] del minDistances[0] print (' '.join(map(str, minDistances))) if __name__ == '__main__': t = int(input()) for t_itr in range(t): nm = input().split() n = int(nm[0]) m = int(nm[1]) distanceMatrix = [dict() for _ in range(n + 1)] for _ in range(m): edge = list(map(int, input().rstrip().split())) i = edge[0] j = edge[1] weight = edge[2] if i not in distanceMatrix[j]: distanceMatrix[i][j] = distanceMatrix[j][i] = weight else: distanceMatrix[i][j] = distanceMatrix[j][i] = min(weight, distanceMatrix[i][j]) s = int(input()) shortestReach(n, distanceMatrix, s)

没有理由在这里使用 heap - queue 就足够了。将节点添加到 queue 的唯一标准是它的距离是否在当前步骤发生了变化。

Hackerrank 测试用例不正确？ Dijkstra 最短距离 2

Hackerrank TestCases are incorrect? Dijkstra Shortest Reach 2

algorithm

graph

dijkstra

python-3.x