[algogeeks] Re: PAIR of shortest paths...
Djikstra's or any other single-source shortest path algorithm should be good enough I guess.-DhyaneshOn 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 -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
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. -DhyaneshOn 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 -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
Why not .. it is a graph with edge weights = 1. In fact we can even just use BFS to solve this problem. I will try and submit a solution and see if what I am thinking is right.-Dhyanesh 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. -DhyaneshOn 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 -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
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 -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
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 right140 3 1 2 31 1 02 2 0 33 2 0 21 2Isn't the answer that camarade 1talks to camarade 0 who inturn talksto 2. Isnt this shortest path algorithm? isntDjikstra 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 -~--~~~~--~~--~--~---
[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 ishttp://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,PradeepOn 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 right140 3 1 2 31 1 02 2 0 33 2 0 21 2Isn't the answer that camarade 1talks to camarade 0 who inturn talksto 2. Isnt this shortest path algorithm? isntDjikstra 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 -~--~~~~--~~--~--~---
