Internet Problem Solving Contest

IPSC 1999

Solution to Problem H – Romeo

Here we provide program solving the problem as well as correct output files for both inputs.

In this problem you could use your knowledge of standard graph shortest path algorithms. Our solution works like this:

  1. First, use Dijkstra's algorithm for computing shortest paths from JS to all other junctions. More precisely for each junction compute the shortest time it takes to get there from JS.
  2. Second, find out, which of the nodes lie on some shortest path to JG. This can be done easily by depth-first search. We start from node JG and from each visited node v we continue to search in all its neighbours u such that if we add edge uv to the shortest path from JG to u, we get a shortest path from JG to v.
  3. After steps 1. and 2. we know for each node whether Juliet can go through this node and if yes, at what time she passes it. Now we repeat steps 1. and 2. for Romeo (i. e. we use RS instead of JS and RG instead of JG).
  4. Juliet and Romeo can meet if there is a node that lies on both some shortest path for Romeo and some shortest path for Juliet and both of them come to this node at the same time. Since we have computed all necessary information for all nodes, we need only to perform a simple check for each node whether it fulfils conditions set above.

Note, that the shortest path, computed here by Dijkstra's algorithms, could be computed also by Floyd-Warshall algorithm, which is easier to implement (but less efficient).