Given an aribtrary graph (possibly with negative weight edge, but no negative weight cycle) and two nodes A and B in the graph. Find the shortest path from A to B with an even number of edges. The graph has at most 1000 vertices and 10000 edges.
The are a number of fire stations in your country. You want each fire station to be able to communicate with each other (either directly or indirectly via other fire stations). There are two ways to for fire stations to communicate with each other: if both fire stations are equipped with satellite communication, they can communicate no matter how far they are. Otherwise, two station can only communicated via radio waves, which requires the stations to be within D distance of each other (Euclidean distance). The larger D is, the more costly it is, so you want to minimize D. Given that that you can install S satellites, where S is less than 100, and the locations of the F fire stations, where F is at most 1000, compute the minimal D. The maximum distance between any two stations is 1000000.