[algogeeks] Re: PAIR of shortest paths...

[shisheng li]

Hi I think this problem is not difficult as u think It is just a flow problem,  with the following constrains   1.       the max flow can pass an edge is 1 2.       the max flow can pass a vertex is also 1, except the first & last vertex   then this is a minimum cost max flow problem (MCMF)     From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On Behalf Of Pradeep Muthukrishnan Sent: Tuesday, October 31, 2006 8:19 AM To: algogeeks@googlegroups.com Subject: [algogeeks] Re: PAIR of shortest paths...   I am sorry , when I spoke to the author of the post he had mentioned a different question which is http://acmicpc-live-archive.uva.es/nuevoportal/contests/contest/index2.php?c=16   problem 2927  in this contest which asks for a pair of shortest paths and so I assumed that he was asking for this question looking at the subject.  I didnt look at the link, which is a totally different problem!!!!. so can ppl help me with problem 2927 which cant be solved using djikstra or atleast not trivially! regards, Pradeep On 10/30/06, Dhyanesh (ધયાનેશ) <[EMAIL PROTECTED]> wrote: I just submitted a solution which uses BFS and passes the judge cases. So it is indeed a shortest path problem. Using Djistra's would be fine too, but as it is here the edge weights are just 1 so BFS works. -Dhyanesh   On 10/30/06, Karthik Singaram L < [EMAIL PROTECTED]> wrote: I am not sure If I got the question right 1 4 0 3 1 2 3 1 1 0 2 2 0 3 3 2 0 2 1 2 Isn't the answer that camarade 1  talks to camarade 0 who inturn talks to 2. Isnt this shortest path algorithm? isnt  Djikstra O(VlogV) which seems feasible for the problem rite? On 10/30/06, Pradeep Muthukrishnan <[EMAIL PROTECTED] > wrote: > I dont see how Djikstra can be used here? > > > On 10/30/06, Dhyanesh (ધયાનેશ) <[EMAIL PROTECTED]> wrote: > > Djikstra's or any other single-source shortest path algorithm should be good enough I guess. > > > > -Dhyanesh > > > > > > > > On 10/30/06, vijay <   [EMAIL PROTECTED]> wrote: > > > > > > Anyone know how to solve this problem... > > >   http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3502 > > > ... > > > I thk its a toughie... > > > > > > > > > > > > > > > > > > > >  > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---