ENG  RUSTimus Online Judge
Online Judge
О системе
Часто задаваемые вопросы
Новости сайта
Архив задач
Отправить на проверку
Состояние проверки
Исправить данные
Рейтинг авторов
Текущее соревнование
Прошедшие соревнования
вернуться в форум

Обсуждение задачи 1930. Машина инженера Ивана

Still WA #11 ?
Послано Hikmat Ahmedov 26 янв 2013 00:38
This test helped me to find my bug. I modified dijkstra algo and added direction array.
9 12
7 3
9 3
9 2
1 2
1 3
4 7
4 1
5 1
4 8
5 8
6 5
2 6
1 8

Edited by author 31.01.2013 17:37
Re: Still WA #11 ?
Послано raven 4 авг 2013 20:04
Thank you
Re: Still WA #11 ?
Послано Akshat Shah 5 май 2020 22:28
Thanks a lot! I was maintaining an array how[], which was storing how to get at that node (uphill mode or downhill node). But that failed Test case #11. I modified the code such that I start Dijkstra's algorithm at the destination node (Orlov's city) as the source node and Ivan's city as the target node. I actually interchanged source with end. So now I think my how[] array stores how one should get here. And it passed all test cases! Does this work because we have no limitation on how to start, but rather how we end makes more impact on the solution? I cannot derive a formal proof. Any comments are welcome