Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
def solution(N, A, B, C):
edges = [(C[i],A[i],B[i]) for i in xrange(len(A))]
edges.sort(key=lambda e: e[0])
maxLenAt = [0]*N
costAt = [0]*N
def updatePath(u,costu,lenu, v,costv, lenv, cost):
if costu < cost and lenu+1 > lenv:
maxLenAt[v] = lenu+1
costAt[v] = cost
elif costu == cost and lenv == 0:
maxLenAt[v] = 1
costAt[v] = cost
for cost,u,v in edges:
cost_u,cost_v = costAt[u], costAt[v]
len_u, len_v = maxLenAt[u], maxLenAt[v]
updatePath(u,cost_u,len_u, v, cost_v, len_v,cost)
updatePath(v, cost_v, len_v, u,cost_u,len_u,cost)
return max(maxLenAt)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment