ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1205. By the Underground or by Foot?

Tips to solve
Posted by guilty spark 9 Sep 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).