Editorial for WC '17 Contest 4 S2 - Strange Travels

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The sanctums and portals form a directed, unweighted graph with $N$ $N$ nodes and $M$ $M$ edges. For each artifact $i$ $i$ , we'll need to compute the shortest distance $D1_i$ $D 1_{i}$ from node $1$ $1$ to node $S_i$ $S_{i}$ , as well as the shortest distance $D2_i$ $D 2_{i}$ from node $S_i$ $S_{i}$ to node $1$ $1$ . If $D1_i$ $D 1_{i}$ or $D2_i$ $D 2_{i}$ are infinite for any $i$ $i$ (in other words, if no paths exist connecting those nodes), then we should output -1. Otherwise, the answer will be the sum of $D1_{1 \dots K}$ $D 1_{1 \dots K}$ and $D2_{1 \dots K}$ $D 2_{1 \dots K}$ .

Computing all of the shortest distances $D1_{1 \dots K}$ $D 1_{1 \dots K}$ can be done in $\mathcal O(N+M)$ $O (N + M)$ time with a standard application of breadth-first search (BFS), starting from node $1$ $1$ .

However, computing the shortest distances $D2_{1 \dots K}$ $D 2_{1 \dots K}$ may be more problematic. We could initiate a separate breadth-first search starting from each node $S_{1 \dots K}$ $S_{1 \dots K}$ , but that approach would be too slow to receive full marks, having a time complexity of $\mathcal O(K(N+M))$ $O (K (N + M))$ . We can instead imagine an alternate version of the graph in which the directions of all edges are reversed (known as the transpose graph). Performing a single breadth-first search on the transpose graph starting from node $1$ $1$ can allow us to compute all of the shortest distances $D2_{1 \dots K}$ $D 2_{1 \dots K}$ in just $\mathcal O(N+M)$ $O (N + M)$ time as well.

Comments

There are no comments at the moment.