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

Обсуждение задачи 1205. На метро или пешком?

Tips to solve
Послано guilty spark 9 сен 2020 20:40
1. Stations may not all be connected. You may have to walk on foot between stations.
2. A and B may be one of the stations or may even be the same point. Maybe the best route is from A to B is on foot without using any stations. Consider all cases.
3. Coordinates are floating points, not integer.
4. Simple dijsktra will work.
5. Use a map to store the node number of the points. If A or B are not one of the stations then give them n and n+1 or n+1 and n+2 (depending on indexing).