176 - City Navigation

[kurtdz]

sorry, is there anyone can provide some testcases for this problem?
i have been stuck by this problem for several days,
here is my test cases:

Code: Select all

A11 1612 1720
A12 1508 1636
S16 1152 1250
S17 1048 1134
S17 1272 1326
#
S16 1288 A11 1543
S18 1202 S18 1102
S18 1202 S18 1101
S18 1202 S18 1206
S18 1202 S18 1203
S17 0902 S17 1044
S17 0906 S17 0902
S17 0902 S17 0906
S17 0905 S17 0903
S17 0903 S17 0905
S17 0903 S17 0907
S16 1100 S16 1000
S16 1101 S16 1000
#

output:

Code: Select all

213
49
151
197
202
176
1
197
198
0
1
49
100

[Quantris]

Hi kurtdz,

My AC program gives the following. Thanks for your cases, they helped me track down my bug(s)!

Code: Select all

213
49
129
197
164
176
1
197
198
0
1
49
100

[LlatzerandToni]

I am getting WA but I can't find a wrong test case... Any hints?

Also, what is the correct output to:

Code: Select all

A01 0100 0200
#
A01 0099 A01 0098
#

0? 200? I think it is not a cul de sac, so 200 must be correct. Anyway, I tried both approaches and judge gives me WA.

Thanks in advance

[lighted]

Try sample tests here. http://contest.mff.cuni.cz/old/archive/ ... index.html

[LlatzerandToni]

Thanks for your help!!! Now I believe that judge is wrong.

I submitted the code of that web and it got AC. But I tested one of the above cases and the answer is not correct, specifically:

Code: Select all

A11 1612 1720
A12 1508 1636
S16 1152 1250
S17 1048 1134
S17 1272 1326
#
S18 1202 S18 1203
#

The AC program outputs 180. I think it fits to the following race:


But this is not the optimal solution. My WA program outputs 164, corresponding to:


I found other different outputs but my path is always shorter... Am I doing something wrong?

Cheers!

[LlatzerandToni]

Someone?