We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
After multiple unsuccessful attempts at the problem and many hours dissecting the editorial, I want to elucidate what the editorial is doing.
This is a commented and clarified version I wrote from my understanding of the editorial thought process.
importsyssys.setrecursionlimit(100000)# Graph is undirected, acyclicM=0# the longest total path between two targetsedgeSum=0# the sum of all edges that must be traversedtargets=[]necessity=[]adj={}defgo(curr,prev):globalM,edgeSum,adj,targets,necessity# The second longest and longest paths downstream from this vertex# in the beginning, there are no paths, so their lengths are -infsecond_longest=-float('inf')longest=-float('inf')forneighbor,costinadj[curr]:ifneighbor!=prev:# don't go back the same way# find the distance covering all the targets when we go in this branchlongest_from_neighbor=go(neighbor,curr)second_longest=max(second_longest,longest_from_neighbor+cost)# swaps when appropriateifsecond_longest>longest:second_longest,longest=longest,second_longest# necessity accounts for the intermediate cities, which are necessary to reach the targetsnecessity[curr]+=necessity[neighbor]# necessary to get to neighbor# this edge is necessary# second term cuts off starting edges if all targets are downstreamifnecessity[neighbor]!=0andnecessity[neighbor]!=k:edgeSum+=cost# two branches lead to targetsifsecond_longest>0:M=max(M,longest+second_longest)# distance from vertex to farthest target downstreamiflongest>0andtargets[curr]:M=max(M,longest)# when it is returned, `second_longest` will get the value `cost`iftargets[curr]:longest=max(longest,0)returnlongestif'__main__'==__name__:# Get inputsn,k=[int(i)foriininput().split()]# targets --> cities Jeanie must go totargets=[Falseforiinrange(n+1)]necessity=[0foriinrange(n+1)]foriininput().split():targets[int(i)]=Truenecessity[int(i)]=1# Forms adjacency list, as a dictionary with tuples entries (neighbor, cost)foriinrange(1,n+1):adj[i]=[]foriinrange(n-1):u,v,d=[int(i)foriininput().split()]adj[u].append((v,d))adj[v].append((u,d))go(1,1)print(edgeSum*2-M)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Jeanie's Route
You are viewing a single comment's thread. Return to all comments →
After multiple unsuccessful attempts at the problem and many hours dissecting the editorial, I want to elucidate what the editorial is doing.
This is a commented and clarified version I wrote from my understanding of the editorial thought process.