백준 알고리즘/Graph1 백준 16958번 - 텔레포트 https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 플로이드-와샬 알고리즘으로 해결 가능한 문제입니다. N이 1000이라 플로이드 알고리즘을 사용하면 시간복잡도가 O(n^3) 이기 때문에 사용하지 못할줄 알았으나 가능했습니다. 텔레포트로 이동하는경우와 맨허튼거리계산과 비교해서 작은 값을 먼저 넣어줍니다. 그 다음에 플로이드 알고리즘을 사용하면 끝~ #include #include #include usin.. 2021. 10. 6. 이전 1 다음