## 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:

- 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**.
- 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**.
- 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**).
- 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).