Page 1 of 1
10269
Posted: Thu May 29, 2003 6:19 am
by Observer
This question looks quite interesting to me.
However, I don't have the slightest idea of how to solve this qq...... :p
Do I have to consider ALL paths before arriving at the answer?
Or are there any better ways to do this qq?
Thx!
_________________________
Beginner............
10269 - Adventure of Super Mario
Posted: Fri Apr 04, 2008 6:26 am
by Jan
Can anyone verify the i/o set?
Input:
Code: Select all
8
1 4 4 61 1
1 2 20
2 3 1
3 4 40
5 4 51
4 1 4 61 1
1 2 20
2 3 1
3 4 40
5 4 51
1 1 1 20 1
1 2 20
6 1 6 100 1
7 6 1
6 5 20
5 4 20
4 3 20
3 2 20
2 1 20
5 2 6 100 1
7 5 1
5 4 20
4 3 20
3 6 20
6 2 20
2 1 20
3 3 5 100 1
6 5 10
6 4 20
5 4 3
4 2 1
2 1 100
4 2 6 5 1
4 6 1
5 6 10
4 5 5
3 5 4
2 3 4
1 2 3
4 2 6 9 1
4 6 1
5 6 10
4 5 5
3 5 4
2 3 4
1 2 3
Is there any tricky case?
Thanks in advance.
Re: 10269 - Adventure of Super Mario
Posted: Mon Sep 08, 2008 7:06 pm
by greve
My solution returns the same output (you can test other sets for the problem on
http://www.uvatoolkit.com).
Re: 10269 - Adventure of Super Mario
Posted: Wed Oct 08, 2008 9:10 am
by warenix
Can anyone explain why uva toolkit gives the following output?
intput
Code: Select all
2
2 1 2 10 1
1 2 8
2 3 10
1 2 2 10 1
1 2 8
2 3 10
output
my program gives:
From my understanding, Mario won't wear boot when the next node is a castle. I wonder why uva toolkit gives 10 for both cases.
Re: 10269 - Adventure of Super Mario
Posted: Wed Oct 08, 2008 3:13 pm
by greve
I thought about the case for some time, and initially thought that there was a bug in my solution, but now I believe that my solution (i.e. the one on uvatoolkit) is correct. The explanation for the second case is as follows. First we go from village 1 to castle 2 for at cost of 8 and then we use the boot from castle 2 to castle 3 for a cost of 0. This gives the total cost of 8. After having reread the problem statement a couple of times I believe that it is allowed to use the boot from a castle to another castle as long as we do not go through an intermediate castle on the way.
Re: 10269 - Adventure of Super Mario
Posted: Wed Aug 31, 2011 8:45 am
by Shafaet_du
try this case,you may find your bug
Code: Select all
2
1 2 2 10 2
1 2 9
2 3 10
2 1 2 10 2
1 2 10
2 3 9
output:
You can start or stop running at any node,but you cant run THROUGH a castle.