1

In http://codility.com/, exist a problem that say:

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.

My main problem is identify the problem. I don't have a heavy background in math. I do the test, it work as the sample data provide in the question, but after submit it, the website say is wrong for this data 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]]

I return -1, but it say I need to return 11. If I start at 0 (home) and try to locate the closer store I get stuck because 0 connect to 8 and 8 lead nowhere. I draw the graph and 0-8 is disconnected from the rest. I suspect is related to http://en.wikipedia.org/wiki/Bridge_(graph_theory) and here is where my knowledge stop.

Is this the proper identification of the problem?

P.D: I'm more interested in understand the problem that have the python code.

4

1 回答 1

0

我将大致解释几种方法，希望你能得到一些想法。如果您自己解决问题，听起来这对您解决问题的能力有好处。

方法 1。

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

方法 2。

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

于 2013-05-25T06:21:30.567 回答