When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Saksham_Sahgal's blog

By Saksham_Sahgal, history, 22 months ago, In English

Given a weighted undirected graph , a source vertex(s) and x distinct vertices as Delivery Location (d1 , d2 , d3 .. dx) assuming that each rider travels at 1m/s what is the min time required to complete all the deliveries if you have M drivers originating from the source simultainously , and also the path followed by them.

( it is guarented that reaching all delivery locations from the source vertex is possible )

input format -

n m s M                            //n vertices , m edges , s is the source vertex , M no of drivers

v11 v12 w1                         //vertices connected with weight w

v21 v22 w2

..

vm1 vm2 wm

x                            // no of delivery locations 1<= x < n

d1 , d2 , d3 , d4 .... dx               //delivery vertices (d[i] != s for all 1 <= i <= x)

output format - (M+1 lines first line should contain the min time required and all others M lines should include paths followed by drivers from 1 to M)

t               //min time to complete all deliveries

1->3->5               // path followed by first delivery guy

1->2->1->5               // path followed by second delivery guy

1->               path followed by third delivery guy (it may be possible that this delivery person didn't moved so his path finished at source only)

(all paths should start from source only)

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

| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems like a pretty standard shortest path problem, where are you stuck at? what have you tried so far?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    the problem is that there are multiple drivers , Eg let the source be 1 and let's say the weights are arranged in such a way, that to do the deliveries in min time , first guy delivers to 7 and 14 while simultaneously second guy delivers to 3 and 6 .

»
22 months ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

It's unclear whether after the delivery the delivery person has to go back to the source. If this is not the case, this problem is NP-hard as TSP can be reduced to this problem with M = 1 and x = n.

And, even if it is the case that the delivery person has to go back to the source after every delivery, the problem is still NP-hard because subset sum problem can be reduced to this problem with M = 2 and x = n (unless edge weight is polynomial in n).

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    No the delivery person doesn't have to go back to source after every delivery , the goal is to complete all deliveries in one go.

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

      So we need more info on the constraints. Like I have mentioned, this problem is NP-hard so you shouldn't expect to come up with any polynomial time algorithm.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I made a visual Simulator version of this problem — Link

        you can check it out if you are interested :>