ACM ICPC Live Archive 3902
ACM ICPC Live Archive 3902 Problem Statement Wrong: Take the root, S, and use Dijkstra's to try to find the shortest path between S and every other leaf. Once an optimal new server is found, repeat the process, but with both S and the new server. Keep adding new servers until the distance is less than or equal to K. Notice that for one thing, this is immensely inefficient in terms of time. It is repeating repeating Dijkstra's. So no. Furthermore, this will not create the most optimal node set. What if the range of one of these new servers overlap with the range of one of the old servers? Lastly, this is complicated beyond need. The following method is simpler: Analysis The "network" is an acylic graph. However, by marking a node, S, on the graph, as a "propagation center", i.e. root, it effectively becomes an directed acylic graph, which can be reorganized into a tree. Notice that the network is an acylic graph. Normally, acyclic graphs don...