11280 - Flying to Fredericton

Moderator: Board moderators

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am

11280 - Flying to Fredericton

I tried Floyd-Warshall but getting WA. Can anyone tell me how to solve this problem?

Thanks.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
this is bellman-ford, not floyd-warshall.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
How you think that this is bellman-ford....

Thanks
Keep posting.

Sapnil

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:
And why DP gets WA?

dp(x,y)
x - vertex
y - max num of stops

dp(0, 0..n) = 0
foreach vertex v connected to vertex 0 dp(v,0) = cost(0,v)

for i := 0...x
dp(x,y) = min{dp(x,y), dp(i, y-1)+cost(i,x)};

Why this gets WA...?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Study bellman-ford if you haven't already.

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:
I know it.
However during the contest I wrote DP...
And now I am just interested why this DP gets WA...?

goodwill
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am

Code: Select all

``dp(x,y) = min{dp(x,y), dp(i, y-1)+cost(i,x)}; ``
It's the same as my AC code and i only considers flight (i,j) where i<j.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My solution is dp, and it works fine. May be you have done something wrong in your implementation.
Ami ekhono shopno dekhi...
HomePage

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:

Code: Select all

``````dp(x,y) = min{dp(x,y-1), dp(i, y-1)+cost(i,x)};
``````
depending on the order of the dp, the above might be more correct.

Masud_CSE_SUST
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
Contact:
what's wrong with my code?

Code: Select all

``code removed after finding mistake``
Can I get some tricky I/O.
Last edited by Masud_CSE_SUST on Wed Sep 19, 2007 6:37 pm, edited 1 time in total.
"Computer science is no more about computers than astronomy is about telescopes." - Dijkstra

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
U have to find the shortest path from Calgary to Fredericton using not more than the requested number of stopovers. U can get a shortest path using (<stop) number of stopovers. It should be considered.

Hope this helps.

Masud_CSE_SUST
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
Contact:
Thanks mmonish for help. I have also a silly mistake. Now waiting to see ....AC
"Computer science is no more about computers than astronomy is about telescopes." - Dijkstra

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
I get too many runtime error.plz help me................

deleted......................

Thanks
Keep posting;
Last edited by sapnil on Fri Sep 21, 2007 11:55 am, edited 1 time in total.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
>>sapnil
U did the same mistake as Masud_CSE_SUST. Read this

Code: Select all

``````Read the problem statement carefully.
U have to find the shortest path from Calgary to Fredericton using not more than the requested number of stopovers. U can get a shortest path using (<stop) number of stopovers. It should be considered.``````
Hope this helps.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
sapnil wrote:I get too many runtime error.plz help me................

Removed.................

Thanks
Keep posting;