Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Network Attack by Sim0000
from heapq import heappush, heappop
def capture(matrix):
n = len(matrix)
q = [(0,0)] # time, node
tmin = {} # dictionary of min time for each node
while(q):
time, node = heappop(q)
if node in tmin: continue # already visited
tmin[node] = time # first visit means min time of node
if len(tmin) == n: break
for i, connect in enumerate(matrix[node]):
if i != node and connect and i not in tmin:
heappush(q, (time + matrix[i][i], i))
return max(tmin.values())
# use heapq as priority queue
# BFS search
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert capture([[0, 1, 0, 1, 0, 1],
[1, 8, 1, 0, 0, 0],
[0, 1, 2, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 3, 1],
[1, 0, 1, 0, 1, 2]]) == 8, "Base example"
assert capture([[0, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 0, 0],
[0, 1, 2, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 3, 1],
[1, 0, 1, 0, 1, 2]]) == 4, "Low security"
assert capture([[0, 1, 1],
[1, 9, 1],
[1, 1, 9]]) == 9, "Small"
June 25, 2014
Comments: