10269 - Adventure of Super Mario

[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............

[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

Output:

Code: Select all

61
51
0
1
40
14
12
9

Is there any tricky case?

Thanks in advance.

[greve]

My solution returns the same output (you can test other sets for the problem on http://www.uvatoolkit.com).

[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

Code: Select all

8
8

my program gives:

Code: Select all

8
10

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.

[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.

[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:

Code: Select all

0
0

You can start or stop running at any node,but you cant run THROUGH a castle.