P2P Conection

解説

親機への送信と親機からの受信において、他の子機を経由することもできるため、直接子機から親機、親機から子機へ送信するよりも早い経路が考えられます。実は、このときの任意のゲーム機$i,j$について、$i \rightarrow j$の送信時間の最小値は、ワーシャルフロイド法を用いることで$O(N^3)$で計算できます。後は、それぞれのゲーム機を親機としたときの残りの全ての子機のうち、最も親機への送信時間がかかるものの送信時間と、最も親機からの受信時間がかかるものの受信時間とを足し合わせた和を求め、それらの最小値を求めて出力すればよいです。この操作は$O(N^2)$で行えます。全体の時間計算量はワーシャルフロイド法がネックとなり $O(N^3)$ ですが、$N \leq 100$ より実行時間制限に十分間に合います。 よって、この問題を解くことができました。