문제풀이

n제한이 1000이라 플로이드 와샬은 할 수 없다.

근데 분류에 플로이도 와샬이 있는걸 보니 뚫리는 거 같다. 플로이드 와샬은 n^3인데 1초에 10억번이나 연산을 칠수있다니 ㄷㄷ

이 텔레포트 문제의 최단거리는 총 3가지이다.
노드 a,b가 있을 때 a,b의 최단거리는
1. a,b사이의 최단거리
2. a,b가 특별한 도시일 때 텔레포트
3. a,b 각각에서 가장 인접한 특별한도시로 가서 텔레포트

위 3가지 경우중 가장 작은 값이 최단거리다.

코드

solution

문제링크

boj/16958