leetcode 743 网络延迟时间

Question

原问题链接：

https://leetcode.cn/problems/network-delay-time/description/

大致问题是：

求指定节点k到其他的每个节点的最短路径，然后将其中最大的最短路径返回

出现的错误：

（应该是存在某个边界的输入出现了问题）

以下是源代码：

python
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        listA=[[] for _ in range(n+1)]
        dictB={(times[i][0],times[i][1]):times[i][2] for i in range(len(times))}#(times[i][0]到times[i][1])的长度是dictB[(times[i][0],times[i][1])]=times[i][2]
        for i in range(len(times)):#listA[i]表示i的邻接
            listA[times[i][0]].append(times[i][1])

        l=[float('inf')]*(n+1)#l[i]是到达i的最短长度
        visited=[False]*(n+1)
        q=deque()
        q.append(k)
        l[0]=0
        l[k]=0 #k到k是0
        while q:#bfs
            top=q.popleft()
            visited[top]=True
            for neighbor in listA[top]:
                if not visited[neighbor]:
                    q.append(neighbor)
                l[neighbor]=min(l[neighbor],l[top]+dictB[(top,neighbor)])#对于top的所有neighbor尝试更新l[neighbor]
        return max(l) if max(l)!=float('inf') else -1 # l更新完了还有inf 则有不可达返回-1

代码思路：

采用BFS遍历这个有向图，同时尝试更新top节点的neighbor的最短路径l[neighbor]=min(l[neighbor],l[top]+dictB[(top,neighbor)])，因为在先前的更新中可以保证l[top]是最小的，所以只需要看l[top]+dictB[(top,neighbor)（先从指定节点k到neighbor，再从top到neighbor）小，还是l[neighbor]（从k直接到neighbor或者是上一步的l值）小

当前的疑问：

我觉得代码已经不存在逻辑漏洞，但是应该还有什么边界条件是我没有考虑到的，由于题目给的51号例子的确不太好debug，所以希望得到各位的解答

Answer 1

引自免费微信小程序：皆我百晓生

经过仔细阅读您提供的代码，发现其中的确存在一个边界条件未处理。在最后的返回语句中，仅通过判断是否存在float('inf')来判断是否存在不可达节点，这是不准确的。因为题目中明确指出节点的编号范围是1到n，因此任何节点的最短路径值不可能是float('inf')。

应该修改代码中的返回语句如下：

return max(l[1:]) if all(l[1:]) else -1

这样的改动将会正确地判断是否存在不可达节点，同时返回最大的最短路径值。

现在，请尝试使用修改后的代码来运行您的测试用例，看看是否能够得到正确的结果。希望对您有帮助！如果您还有其他问题，请随时提问。