10740 - Not the Best

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sun Oct 24, 2004 6:41 pm

What reference do you need? Isn't slightly modified Dijkstra (with counting the k-th shortest path to all the verticles) good enough?
No, it isn't. It is not inmediately clear how to deal with zero-length cycles.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Oct 25, 2004 1:30 am

I don't really get what's wrong with zero-length circuits. You should visit a verticle only if it's k-th shortest path from the source isn't already known. So if you have zero-length circuit, you should take it at most k times.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Tue Feb 22, 2005 2:37 am

Hi,
could anyone give more test cases to check my program...,
is there exist any special test case?

TIA.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Tue Feb 22, 2005 3:08 pm

thx, i found my mistake...

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

10740 "Not The Best" ...Please Inputs!!!

Post by chuzpa » Fri Apr 15, 2005 11:57 pm

I removed my code :$, It has been long enogh here haha, enjoy the problem ..
Last edited by chuzpa on Tue Oct 20, 2009 11:37 pm, edited 1 time in total.

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

hi there...

Post by chuzpa » Sat Apr 23, 2005 7:40 pm

Hi nobody answered me ... :s hahaha but it is accepted now ....

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Mon Nov 19, 2007 5:08 pm

I use the MPS algorithm introduced in the article The K shortest paths problem from this page. It's fast.
I stay home. Don't call me out.

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 10740 - Not the Best

Post by prashantharshi » Thu May 29, 2014 1:40 pm

using algo similar to bellman ford and heap
http://ideone.com/WuY91C
getting WA :(
need help

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10740 - Not the Best

Post by brianfry713 » Wed Jun 11, 2014 11:28 pm

Try using a modified Dijkstra's algorithm.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 107 (10700-10799)”