_Aryan_'s blog

Minimum time to deliver k letters
By _Aryan_, history, 17 months ago, In English

Byteland has N cities (numbered from to ) and N-1 bidirectional roads. It is guaranteed that there is a route from any city to any other city.

Jeanie is a postal worker who must deliver Kletters to various cities in Byteland. She can start and end her delivery route in any city. Given the destination cities for K letters and the definition of each road in Byteland, find and print the minimum distance Jeanie must travel to deliver all K letters.

Note: The letters can be delivered in any order.

The first line contains two space-separated integers, N (the number of cities) and K (the number of letters), respectively. The second line contains K space-separated integers describing the delivery city for each letter. Each line i of the N-1 subsequent lines contains 3 space-separated integers describing a road as ui,vi,di , where di is the distance (length) of the bidirectional road between cities ui and vi.

sample:
5 3
1 3 4
1 2 1
2 3 2
2 4 2
3 5 3

output:
6

path:3-2-1-2-4

approach for this problem

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is V here?? O(V+E) Also are the edges weighted or assumed weight = 1

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    linear solution indended V->vertices yes weighted

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Aryan_ (previous revision, new revision, compare).

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Aryan_ (previous revision, new revision, compare).

→ Reply
»
17 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
1) if there is a city (that we want to deliever parcel) is ancestor of other
than when we go to its descendent we must go through it. so we don't care all these types of cities
2) when there is no parcel in its subtree, then all delete that types of edges , we don't need them
3)Now our tree is like , there is only parsels at the leaf nodes. (whose deg =1)

UPD: https://www.hackerrank.com/challenges/jeanies-route/problem Same Problem

→ Reply
»
17 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

First, notice that you only care about the deepest nodes because you when you visit a node you will always visit its children next (else you're doing some suboptimal path). Also notice we won't go down a subtree that has no delivery node. Thus the problem is reduced to visiting the K leaves. It is easy to solve if the weights are all one so you can generalise this approach

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it 
    I have discussed the same idea.
I am thinking like , let we start from a leaf and end at the same leaf
Now given that we can stop when we are done , so Ans = total_time - time(last_leaf , start_leaf)
for this to be min, time(last_leaf , start_leaf) should be maximum
Which is the diameter for the new tree
    → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The following approach only works if the distance between any two cities is non-negative.

A possibility is to get the minimum distance of passing through all of them and then returning to the start(starting on one of the $$$K$$$ cities) then subtract the maximum distance between two special nodes. Both calculations can be done with a relatively simple dfs/bfs. This has the significance of starting from one of the nodes and running to all of them and stopping at the other special node.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got the final solution done, but just wondering if this is solvable by finding minimum spanning tree and centroid then find all k nodes' distance from centroid?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you find the minimum spanning tree of a tree?

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok nvm i didnt see notice its a tree itself

      → Reply