10171 - Meeting Prof. Miguel...

[Chow Wai Chung]

Do you correct with the test data i had posted?? There may be more than one place have 0 cost when me and prof. on the same place.

I also use Dijkstra twice to find minimal cost paths in graph to solved this problem

[angga888]

Hi Dominik...
Have you consider when your or prof. city has no connection with the others cities?

Try these inputs:

Code: Select all

2
Y U A B 0
M U A B 0
A C
2
Y U A B 0
M U A B 0
C C

And my AC solution outputs:

Code: Select all

You will never meet.
0 C

Try them.
Good Luck!

angga888

[Dominik Michniewski]

Yes I consider such cases ... I also try using Floyd, but I got WA too ...
I guess that I have some IO problem , but I don;t know which is it .... all tests, which I found or which are sended to me my program solved correctly. This problem drive me crazy - looks easy but I have a lot problems with it :(:(:(

Best regards
DM

[Dominik Michniewski]

Finally I got it. I did small mistake -incorrect type of one variable. and accepted with this minor change :)

Thank all very much for help and test cases

Best regards
DM

[Whinii F.]

After some nasty submissions & WAs, I found out they have some self-loops in the input. (Can be crucial to some who used Floyd's algo like me..)

[deddy one]

CUT.......

Got Ac now.

I failed in this test case :

Code: Select all

4
Y U A B 3
M B B A 0
Y B C A 10
M U B D 1
A B

the answer is obvious so I wouldn't tell.

ciaoo...

[Mahmud776]

I am getting WA, my program passed all the input given in this post, can someone provide me with a case where my program fails.

I think my code is ok,i checked every line.But there was nothing wrong.At least i did not find anything.Could anyone help me.
[cpp]
cut. As i got accepted.So i cut this.

[/cpp]

[MD.Morsalin-Al-Saadi]

hi mahmud,
try yourself. You should modify a little.

[Mahmud776]

Hi morsalin,

I want specific help! But what you said is known to me.I think this is known to all.

[shamim]

Mahmud, You are not considering the fact there could be more than one path from one point to another. In that case you must use the path with lowest cost.

That is whether the cost should be updated depends on its current value.
Good Luck.

[Mahmud776]

Thanks Shamim,
Thanks for your helps, after some modifications according to your advices i got accepted. You are a great helper.
---Mahmud

[dvntae]

i'm a bit confused about printing the lexographical order of possible places.
consider this test case:

2
Y B A B 2
M B B A 5
A B

Would the output should be:
2 B A
-> B is printed first because the minimum energy is 2, or:

2 A B
-> print the minimum energy, afterwards all the possible places in lexographical order.

i tried using floyd, with special modification to handle the self loops. for all the previous inputs in this thread, it handle correctly. but still got some minor problem i guess... and i dun have many time to think bout it coz i'd prefer to go out and play >_<

so please help me with anymore testcases...

[rakeb]

the output should be
2 B
because shahriar manzoor will go to B using cost 2
and Prof. Miguel will stay in B so he uses cost 0.

try this data

4
Y B A B 2
Y U B D 0
M B B C 3
M U B D 0
B B
output is
0 B D

[jackie]

After many WAs i got AC finally.

I use floyed algorithm to compute all pair shortest distance (just for the simple code).

My program is ok for all the input above but the judge said WA. I generate a case and it's about many U or B roads connecting two cities.

2
Y U A B 10
Y U A B 100
A B
0

hope it will help for those who get WA.

BTW pay attention to the input

i use
[cpp]
scanf(" %c %c %c %c %d", &d1, &d2, &d3, &d4, &len);[/cpp]
good luck[/quote]

[helloneo]

i tested all the cases on this board..
it seems to be all right..
but i still get WA..
help plz.. ㅠㅠ

Code: Select all

CUT AFTER AC