ABC012D

https://gyazo.com/ee05f83557e61f16cca327eded5de119

考えたこと

最も遠い頂点までの距離が最小になる点を選んだ時の、その距離を求める問題だと

全方位木DPで求めるんだったかな

そんな難しいことをこの難易度で聞かれるかな

あっ、これ木じゃないぞ？

Vは300なので間に合う？

公式解説

「ただしPythonなどの遅い言語では通らないことが検証済み」(ええー)

ダイクストラをO((E+V)log V)でやる案

これ試してみよう

PythonでもあっさりACしました

5秒制限のところ1.4秒

6年前の問題だからジャッジマシンが早くなったのかな？

それとも「通らないことが検証済み」ってのはV^3の解法のことかな

code:python

def solve(N, M, edges):

INF = 9223372036854775807

ret = INF

for start in range(N):

while queue:

d, frm = heappop(queue)

# already know shorter path

continue

# found shorter path

ret = min(ret, max(distances))

return ret