BOJ 5551 - 쇼핑몰
어떤 쇼핑몰에서 최단거리 $d_i, d_j$ 가 있고 $i,j$ 를 연결하는 $w$가중치 간선이 있다고 하자.
$\vert d_i-d_j \vert \ge w$ 라면 볼 필요가 없고(작은 최단거리를 가진 정점에서 큰 최단거리를 가진 정점으로 도달해버리는 시간이 더 빨라서 중간에 집이 있을 필요가 없어서)
그렇지 않다면 최단거리가 더 짧은 간선에서 ${\vert d_i-d_j \vert}$ 만큼 더 이동한 다음 남은 $w - \vert d_i-d_j \vert$ 만큼은 두 정점에서 동일하게 가질 것이므로
최단거리가 긴 간선에서 $\dfrac{w-\vert d_i-d_j \vert}{2}$ 만큼 더 걸리는 중간 지점에 집을 지어서 정답 후보로 검사해주면 된다.
Comments