텔레포트
-
백준 16958번 텔레포트PS 2020. 2. 14. 14:19
https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다. 두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자. www.acmicpc.net 특별 도시 사이에는 텔레포트가 가능합니다. 텔레포트가 직접 걸어서 가는 것보다 무조건 빠른 것은 아닙니다. 그러므로 직접 비교해봐야합니다. 따라서 다음과 같은 경우가 발생합니다. 1. 일반 -> 일반 1-1. 걸어간다 1..