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