In the plane with integer coordinates, there are X start points and Y endpoints (X=Y). There are also some obstacles in the plane (unwalkable points). The task is to find path from each X to exactly one Y (each Y can be endpoint for exactly one X) such as the sum of all paths ar minimized.
The size of plane is 10^6 x 10^6, max number of start points is 20. There may be 200 rectangular obstacles. Time limit is 10 seconds, memory limit 4GB
I'm considering using A* algorithm to compute shortest paths from each X to each Y, but I'm afraid that it wont be sufficient couse 20x20 times use of A* could be a bit time consuming.
Maybe there is some better algorithm for finding paths from each X to each Y?
