python - 这与图切边(桥)有关吗？及时找到从家到商店/商店的快速路径

Question

在http://codility.com/ ，存在一个问题说:

There are N squares in your neighborhood and M direct roads connecting them. The squares are numbered from 0 to N − 1. You are living in square 0 and can reach it in 0 seconds. The stores are located in the squares, one in each of them. You are given a map of the neighborhood in the form of four zero-indexed arrays A, B, C and D. Each of the arrays A, B, C contains M integers, while D contains N integers. For each I (0 ≤ I < M), the walking distance between squares A[I] and B[I] is C[I] seconds (in either direction)

There can be multiple roads connecting the same pair of squares, or a road with both ends entering the same square.

It is possible that some roads go through tunnels or over bridges (that is, the graph of squares and roads doesn't have to be planar).

It is not guaranteed that you are able to reach all the squares. For each J (0 ≤ J < N), the shop at square J will close in D[J] seconds (if D[J] = −1, then the store is already closed); it is possible to buy the food even if you reach the shop at the very last second, when it closes. Write a function:

int solution(int A[], int M, int B[], int M2, int C[], int M3, int D[], int N);

that, given arrays A, B, C and D, returns the minimum time (in seconds) needed to reach an open store. If it is impossible, it should return −1.

我的主要问题是找出问题所在。我的数学背景不深。我做了测试，它按照问题中提供的样本数据工作，但是提交后，网站说这个数据是错误的data = [[6, 6, 3, 8, 8, 6, 7, 5, 1, 4, 3, 2, 7, 7], [3, 7, 5, 8, 0, 6, 3, 4, 1, 7, 1, 5, 3, 2], [8, 1, 9, 12, 11, 1, 8, 12, 3, 6, 12, 7, 4, 2], [-1, 1000000000, 1000000000, 999999999, 999999999, 999999999, 1000000000, 1000000000, 1000000000]]

我返回 -1，但它说我需要返回 11。如果我从 0(家)开始并尝试找到更近的商店，我会卡住，因为 0 连接到 8，而 8 无处可去。我画了图，0-8 与其余部分断开了连接。我怀疑与http://en.wikipedia.org/wiki/Bridge_(graph_theory)有关这是我的知识停止的地方。

这是对问题的正确识别吗？

P.D:我更感兴趣的是理解有 python 代码的问题。

Answer 1

我将粗略地解释几种方法，希望您能从中得到一些想法。如果您自己解决问题，听起来这对您解决问题的能力很有帮助。

方法 1。

使用二分查找计算最短时间。对于二进制搜索中的每个猜测，都有一个函数可以计算出是否有可能在那个时间到达商店。 (如果可能，减少时间，否则增加时间)。您可以通过深度优先搜索或广度优先搜索(停止在比猜测更远的节点上)来检查是否可能。

方法 2。

使用 python 的 heapq 数据结构。从 [(0, start)] 的初始堆开始，其中 0 是距离 0，start 是起始节点。然后对于每个连接到start的节点x，heappush(0 + dx, x)到heapq(dx是start到x的距离)。现在开始。现在弹出下一个最佳节点。检查距离是否小于 D[x]。继续。