best algorithm for given problem

[artartart]

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?

[WingedPanther]

You may want to find the closest Y for each X. If there are any conflicts, find the first and second closest Y for each X, look for a non-conflict mix. Repeat as necessary.