Editorial for Another Random Contest 1 P6 - Smash Bros

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.

Author: andy_zhu23

Subtask 1

Since node $A$ ~A~ is equal to $X$ ~X~, Andy can go straight to $Y$ ~Y~. Thus, the answer is the shortest distance from $X$ ~X~ to $Y$ ~Y~.

Time Complexity: $\mathcal O(M \log N)$ ~\mathcal O(M \log N)~

Subtask 2

Let's call the shortest distance between $U$ ~U~ and $V$ ~V~ to be $d_{u,v}$ ~d_{u,v}~.

For any point $A$ ~A~, there must exist a point $Z$ ~Z~ such that the shortest path goes $X \to Z \to A \to Z \to Y$ ~X \to Z \to A \to Z \to Y~. This path results in a cost of $d_{X,Z} + d_{Z,A} + d_{Z,Y}$ ~d_{X,Z} + d_{Z,A} + d_{Z,Y}~ ( $d_{A,Z}$ ~d_{A,Z}~ is ignored because all nodes on the path have already been unlocked when traversing from $Z$ ~Z~ to $A$ ~A~).

Building on that, let's analyze $d_{X,Z} + d_{Z,A} + d_{Z,Y}$ ~d_{X,Z} + d_{Z,A} + d_{Z,Y}~.

$d_{X,Z} + d_{Z,A} + d_{Z,Y}$ ~d_{X,Z} + d_{Z,A} + d_{Z,Y}~ can be separated into two parts, $d_{X,Z} + d_{Z,Y}$ ~d_{X,Z} + d_{Z,Y}~ and $d_{Z,A}$ ~d_{Z,A}~. $d_{X,Z} + d_{Z,Y}$ ~d_{X,Z} + d_{Z,Y}~ doesn't depend on $A$ ~A~, and can be precomputed by running shortest path twice from nodes $X$ ~X~ and $Y$ ~Y~. For every query, run shortest path from node $A$ ~A~ and determine the minimum value of $d_{X,Z} + d_{Z,A} + d_{Z,Y}$ ~d_{X,Z} + d_{Z,A} + d_{Z,Y}~ for all possible node $Z$ ~Z~.

Time Complexity: $\mathcal O(QM \log N)$ ~\mathcal O(QM \log N)~

Subtask 3

Set up an additional node $O$ ~O~, and build new edges with every single node in the graph. The edge between $O$ ~O~ and any node $U$ ~U~ is going to have a weight of $d_{X,U} + d_{U,Y}$ ~d_{X,U} + d_{U,Y}~. Run shortest path algorithm from node $O$ ~O~, and the shortest path from node $O$ ~O~ to any node $U$ ~U~ is the answer for when $A = U$ ~A = U~. Thus, each query can be answered in $\mathcal O(1)$ ~\mathcal O(1)~.

Time Complexity: $\mathcal O(M \log N + Q)$ ~\mathcal O(M \log N + Q)~

Comments

There are no comments at the moment.