Can Anyone Help me in this Graph Question ?

Revision en1, by Saksham_Sahgal, 2022-05-07 09:41:00

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                            //n vertices and m edges s is the source vertex

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)

Tags graphs, dp, dp on graphs


  Rev. Lang. By When Δ Comment
en2 English Saksham_Sahgal 2022-05-07 18:07:17 41 Tiny change: 'rmat -** (m+1 lines f' -> 'rmat -** (M+1 lines f'
en1 English Saksham_Sahgal 2022-05-07 09:41:00 2333 Initial revision (published)