graph problem

Правка en1, от Onesh0t, 2018-10-20 00:54:50

Hey can someone please help.this question was asked in an interview. There are N points on a 2D- grid in the form (x,y). The distance between any two points x1,y1 and x2,y2 is=|x1-x2|+|y1-y2|. We have to traverse all the points starting from any one such that the total distance travelled by you is minimum. But, there are M restrictions, in the form u,v such that you cannot traverse v after covering u.
Eg- input- 5 (N=Number of points) (x,y coordinates of these points) 1,1 2,2 3,3 4,4 5,5 (M=number of restrictions) 2 1 2 (meaning you cannot traverse 2nd point(2,2) after covering 1st(1,1)) 3 4 (meaning you cannot traverse 4th point(4,4) after covering 3rd(3,3)) output-8 explanation--- > traverse in the order (5,5 ------>4,4------>3,3----> 2,2---> 1,1)

Теги #graph, all-shortest-path

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Onesh0t 2018-10-20 00:54:50 799 Initial revision (published)