| ENG RUS | Timus Online Judge |
Обсуждение задачи 1325. Грязь黄源河 The problem was impossible to accept!!! [22] // Задача 1325. Грязь 22 апр 2004 21:14 Vladimir Yakovlev (USU) It is possible! [21] // Задача 1325. Грязь 22 апр 2004 22:14 黄源河 Re: It is possible! [20] // Задача 1325. Грязь 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 Vladimir Yakovlev (USU) I used Dijkstra algorithm with Heap. [1] // Задача 1325. Грязь 23 апр 2004 11:58 SkorKNURE Re: I used Dijkstra algorithm with Heap. // Задача 1325. Грязь 16 ноя 2008 22:13 Dijkstra via STL priority_queue<> ~0.25 sec Dijkstra via hand-written heap implemented with change_priority() function ~ 0.125 sec Oberon (Yura Znovyak) I have solved it with 2 BFS [17] // Задача 1325. Грязь 27 апр 2004 06:12 Failed Peter Re: I have solved it with 2 BFS [16] // Задача 1325. Грязь 28 апр 2004 13:35 how? Oberon (Yura Znovyak) 1 BFS for finding shortest amount of boot change. Another one for shortest path. [15] // Задача 1325. Грязь 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. Zieve Cheng Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. [4] // Задача 1325. Грязь 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. Oberon (Yura Znovyak) Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. [3] // Задача 1325. Грязь 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 Korduban [Kiev] Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. [2] // Задача 1325. Грязь 6 авг 2004 15:28 It's very nice method! I have got AC in 0.203s Denis Koshman Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. [1] // Задача 1325. Грязь 21 авг 2008 04:00 Try this test: 6 5 1 3 6 3 11111 12222 11112 12222 11112 22222 Correct answer: 7 1 So, after 1st BFS both components stay alive. What would prevent 2nd BFS from going a vertical line and output "6 1" while assumed path yields "6 5"? Ta'al Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. // Задача 1325. Грязь 15 май 2014 13:37 I'm sorry, but can anybody describe me 2nd BFS? I spent a lot of time trying, but it give me wrong answer on some tests. Vladimir Yakovlev (USU) It's right solution. It has implementation in O(N*M). [7] // Задача 1325. Грязь 28 апр 2004 22:59 Zieve Cheng Re: It's right solution. It has implementation in O(N*M). [6] // Задача 1325. Грязь 29 апр 2004 12:10 Now I know that's used colouration. Edited by author 29.04.2004 16:37 Dmitry 'Diman_YES' Kovalioff Of course, Dijkstra + Heap should get AC (-) [5] // Задача 1325. Грязь 29 апр 2004 16:54 Oberon (Yura Znovyak) I got TL on test 16 :( (-) // Задача 1325. Грязь 29 апр 2004 16:58 Zieve Cheng Re: Of course, Dijkstra + Heap should get AC (-) [3] // Задача 1325. Грязь 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 hello Re: Of course, Dijkstra + Heap should get AC (-) [2] // Задача 1325. Грязь 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 ? Zieve Cheng Re: Of course, Dijkstra + Heap should get AC (-) [1] // Задача 1325. Грязь 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 ? hello Re: Of course, Dijkstra + Heap should get AC (-) // Задача 1325. Грязь 26 июн 2004 11:32 Thanks . I just uesd 0.187s to get AC ! Failed Peter Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. [1] // Задача 1325. Грязь 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? Oberon (Yura Znovyak) Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. // Задача 1325. Грязь 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. |