11280 - Flying to Fredericton

Donotalo · Post by **Donotalo** » Mon Sep 17, 2007 12:46 am

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

Thanks.

sclo · Post by **sclo** » Mon Sep 17, 2007 1:36 am

this is bellman-ford, not floyd-warshall.

sapnil · Post by **sapnil** » Mon Sep 17, 2007 7:32 pm

How you think that this is bellman-ford....

Thanks
Keep posting.

Sapnil

Lomir · Post by **Lomir** » Mon Sep 17, 2007 10:24 pm

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 · Post by **sclo** » Mon Sep 17, 2007 10:54 pm

Study bellman-ford if you haven't already.

Lomir · Post by **Lomir** » Mon Sep 17, 2007 11:31 pm

I know it.
However during the contest I wrote DP...

And now I am just interested why this DP gets WA...?

goodwill · Post by **goodwill** » Tue Sep 18, 2007 1:03 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 · Post by **Jan** » Tue Sep 18, 2007 1:21 am

My solution is dp, and it works fine. May be you have done something wrong in your implementation.

sclo · Post by **sclo** » Tue Sep 18, 2007 1:57 am

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 · Post by **Masud_CSE_SUST** » Wed Sep 19, 2007 1:53 pm

what's wrong with my code?

Code: Select all

code removed after finding mistake

Can I get some tricky I/O.

mmonish · Post by **mmonish** » Wed Sep 19, 2007 2:41 pm

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.

Masud_CSE_SUST · Post by **Masud_CSE_SUST** » Wed Sep 19, 2007 6:41 pm

Thanks mmonish for help. I have also a silly mistake. Now waiting to see ....AC

sapnil · Post by **sapnil** » Thu Sep 20, 2007 5:24 pm

I get too many runtime error.plz help me................

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

Thanks
Keep posting;

mmonish · Post by **mmonish** » Fri Sep 21, 2007 2:16 am

>>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 · Post by **sapnil** » Fri Sep 21, 2007 6:31 am

sapnil wrote:I get too many runtime error.plz help me................

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

Thanks
Keep posting;