Блог пользователя _Aryan_

Minimum time to deliver k letters
Автор _Aryan_, история, 10 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
10 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
10 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится 
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

→ Ответить
»
10 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 месяцев назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится 
    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
    → Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить