Educational Codeforces Round 161 (Rated for Div. 2) のC問題 (Closest Cities) の解説記事です。

問題 個の町があり、これらの町の間には 本の道路があり、道路 は町 と町 を結び、その長さは である。 また、どの町にも必ず自転車が1台売られており、町 での自転車の速度指標は である。 ここで速度指標とは、その自転車を使用することにより掛かる時間の…

問題 頂点からなる木構造のグラフと、整数 が1個ずつランダムに入った順列 が与えられる。 ここで、グラフ内の頂点 の距離を とする。 組の整数 が与えられるので、そのそれぞれについて が成立するような が の中に含まれるか判定せよ。 入力 まず最初の1行…

問題 個の街が2次元平面上にあり、それぞれ街 と名付けられており、このうち最初の 個は主要都市である。 街 の座標は である。 ここで、街 から街 へと移動する際には費用 がかかる。 については がともに主要都市のとき: それ以外のとき: で与えられる。 …