2745

寝る前にソースが見つかって助かった(´･ω･｀) 去年解いたグラフの問題。必要なルータの個数とそのルータの次数を出力する。

とりあえず適当に二つのルータを繋げる。そうすると、新たなPCを追加するときは、既存のルータから新たな線を延ばさないといけない。追加されるPCから既存のPCまでの距離は

• 既存のPC1から追加されるルータまでの距離+そのルータから追加される場所までの距離
• 既存のPC2から追加されるルータまでの距離+そのルータから追加される場所までの距離

となるので、それを満たすルータを探してやればいい。後半は両式で等しくなるので、追加されるPCをPC3とすると

distance(PC1, PC3) - distance(PC1, ルータ) == distance(PC2, PC3) - distance(PC2, ルータ)

を満たすルータに追加してやれば良いことがわかる。後は追加するルータが一つになるまで処理を繰り返せばいい。追加したらまた次のPCを同じ方法で追加。