Обсуждение @ 1325. Грязь @ Timus Online Judge

Страницы: 1 2 Следующая

The problem was impossible to accept!!!

Послано 黄源河 22 апр 2004 21:14

It is possible!

Послано Vladimir Yakovlev (USU) 22 апр 2004 22:14

see this:
http://acm.timus.ru/status.aspx?space=1&pos=574747

Re: It is possible!

Послано 黄源河 23 апр 2004 11:27

How can you do it, I'am puzzled. Can you solve it today???

Edited by author 23.04.2004 11:29

I used Dijkstra algorithm with Heap.

Послано Vladimir Yakovlev (USU) 23 апр 2004 11:58

I have solved it with 2 BFS

Послано Oberon (Yura Znovyak) 27 апр 2004 06:12

Re: I have solved it with 2 BFS

Послано Failed Peter 28 апр 2004 13:35

how?

1 BFS for finding shortest amount of boot change. Another one for shortest path.

Послано Oberon (Yura Znovyak) 28 апр 2004 17:47

First. You can contract all regions in one vertex.
Second. You can find shortest distance by regions.
Third. Remove useless regions. BFS what was left.

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Послано Zieve Cheng 28 апр 2004 21:47

I don't agree your opinion.The method can't work out in time.This method I had used to solve,but fail.

Oberon (Yura Znovyak) писал(a) 28 апреля 2004 17:47

First. You can contract all regions in one vertex.
Second. You can find shortest distance by regions.
Third. Remove useless regions. BFS what was left.

It's right solution. It has implementation in O(N*M).

Послано Vladimir Yakovlev (USU) 28 апр 2004 22:59

Re: It's right solution. It has implementation in O(N*M).

Послано Zieve Cheng 29 апр 2004 12:10

Now I know that's used colouration.

Edited by author 29.04.2004 16:37

Of course, Dijkstra + Heap should get AC (-)

Послано Dmitry 'Diman_YES' Kovalioff 29 апр 2004 16:54

I got TL on test 16 :( (-)

Послано Oberon (Yura Znovyak) 29 апр 2004 16:58

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Послано Oberon (Yura Znovyak) 29 апр 2004 17:04

Zieve Cheng писал(a) 28 апреля 2004 21:47

I don't agree your opinion.The method can't work out in time.This method I had used to solve,but fail.
Why?
I have impelemnted in O(N*M) --> AC in 0.359 s

Re: Of course, Dijkstra + Heap should get AC (-)

Послано Zieve Cheng 29 апр 2004 17:29

But it wastes much time,such as me,used 0.906s to accept.And I used many optimize skill to make it run fast and get accept so hard.
http://acm.timus.ru/status.aspx?space=1&pos=582582

Dmitry 'Diman_YES' Kovalioff писал(a) 29 апреля 2004 16:54

Now I used colouration and got accepted in short time,only 0.234s.And the method carry out easily.
http://acm.timus.ru/status.aspx?space=1&pos=583722

Edited by author 30.04.2004 17:44

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Послано Failed Peter 7 май 2004 18:38

but i think it's possible that such condition appears:

in the first BFS to find shortest distance by Changing Boots,there may be many ways to get the shortest Changes.
but these ways are different in shortest way of Walking.
So?

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Послано Oberon (Yura Znovyak) 7 май 2004 23:04

I do not understand :(

Failed Peter писал(a) 7 мая 2004 18:38

in the first BFS to find shortest distance by Changing Boots,there may be many ways to get the shortest Changes

First BFS is for

Failed Peter писал(a) 7 мая 2004 18:38

shortest distance by Changing Boots

Then we throw away all useless regions and use SECOND BFS for

Failed Peter писал(a) 7 мая 2004 18:38

shortest way of Walking

Of course for each region we store min boot change to get to it. While finding shortest walking distance we almost ignore regions. Why almost: we make jumps only on regions with higher boot changes. So we can avoid saw-like regions.

Re: Of course, Dijkstra + Heap should get AC (-)

Послано hello 17 май 2004 17:40

So fast !!!!!!
I got TLE on test 16 all the time ........
I don't know what does "colouration" mean .
Could you explain ?
Could you say your way ?

Re: Of course, Dijkstra + Heap should get AC (-)

Послано Zieve Cheng 20 май 2004 18:47

Oberon (Yura Znovyak) had told the method very clarity.

hello писал(a) 17 мая 2004 17:40

So fast !!!!!!
I got TLE on test 16 all the time ........
I don't know what does "colouration" mean .
Could you explain ?
Could you say your way ?

Re: Of course, Dijkstra + Heap should get AC (-)

Послано hello 26 июн 2004 11:32

Thanks .
I just uesd 0.187s to get AC !

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Послано Korduban [Kiev] 6 авг 2004 15:28

It's very nice method! I have got AC in 0.203s

Страницы: 1 2 Следующая

Обсуждение задачи 1325. Грязь