python-3.x - Hackerrank 测试用例不正确？ Dijkstra 最短距离 2

Question

Hackerrank - Dijkstra 最短距离 2

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

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

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

HackerRank Platform 经常出bug吗？

在为我的求职面试做 HackerRank 挑战时，我经常遇到一个不明显的失败(通常是 13 个测试用例中的最后一两个)，因此多次失败。不知道大家有没有类似的经历。我怀疑当我和 friend 一起检查我提交的代码时，我们找不到任何边缘情况或错误。它应该是完美的。作为一直在 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 drive 文件夹中，我附上了我的输出:output_me.txt 和 ground truth 输出: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 来除某物因为它在本地工作。还有什么？根据Hackerrank Environment对于 Python，内存限制为 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 .因此，请尝试降低解决方案的空间复杂性。

我还注意到另一个问题 - 如果您使用 time 来衡量时间复杂度模块那么它需要超过40 测试用例 #7 完成的秒数。因此，如果您先解决空间复杂度问题，这可能是您的下一个问题。

最后，不，这里没有关于 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 的唯一标准如果它的距离在当前步骤发生了变化。