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.
To check if a hotel can be located in a particular node (city), it is sufficient to calculate the minimum
distances from that node to all others using the breadth-first search algorithm and then compare the
obtained distances with the given distances from the task. If they match (except where 
~d_i = -1~), the
hotel can be located in that node. The complexity of this check is 
~\mathcal{O}(n+m)~.
In the first and third subtasks, we check for each node in the same way whether a hotel can be located in
it. The overall complexity is 
~\mathcal{O}(n(n+m))~.
In the second subtask, we are looking for nodes that are at a distance of 
~d_1~ from city 
~1~. A special case is
when all ~d_i = -1~, in which case the hotel can be in any node. We only run breadth-first search for one
city, so the complexity is ~\mathcal{O}(n+m)~.
In the final subtask, we run multisource BFS. Instead of calculating distances for each node separately, we
compute them simultaneously for all nodes. The idea is to calculate, for each node 
~i~, 
~h_i~ – the distance of
that node from the hotel, and 
~S_i = \{x \mid h_i + d(i, x) = d_x \ne -1\}~ where 
~d(x, i)~ is the distance between
nodes 
~x~ and ~i~. In simple terms, 
~S_i~ is the set of all nodes ~x~ from which we could obtain the given ~h_i~ (those
where distances ~h_i~ and 
~h_x = d_x~ are not contradictory). The hotel can only be in nodes for which 
~h_i = 0~
and 
~S_i = \{x \mid d_x \ne -1\}~.
Starting from the node with the largest distance 
~d_i~, we perform a breadth-first search, simultaneously
adding nodes whose distance from the hotel equals the distance of the node in the current iteration of the
algorithm. If, from node ~i~, we observe an edge to a node 
~j~ that we have already visited, and 
~h_j+1 = h_i~,
we add all nodes from set ~S_i~ to set 
~S_j~.
Set ~S_i~ can have a size of 
~n~, so the complexity is not significantly improved. However, notice that bitset
supports all necessary operations! The overall complexity then becomes 
~\mathcal{O}(m \times \frac{n}{64})~, and it is sufficient to
solve the entire task.
You can find more about this structure at the link.
Comments