제가 생각한 알고리즘은 이렇습니다. A-B를 A와 B를 잇는 최단거리 혹은 A에서 B로 가는 최단경로라고 생각해주세요.

G와 H중 S와의 최단거리가 더 먼 점을 A라고 두고,

S-T가 S-A + A-T와 같다면 T는 가능한 목적지라고 판단합니다.

제가 G와 H중 더 멀리 떨어져 있는 점 하나만 고려한 이유는 다음과 같습니다.

우선 최단경로를 구성하는 요소들을 최단경로로 이루어져 있습니다.

예를들어 S에서 T까지의 최단경로가 S-X-Y-Z-T라면, X에서 Z까지의 최단경로는 X-Y-Z입니다.

문제에서 G-H(혹은 H-G)가 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부라고 알려주었습니다.

만약 S-H가 S-G보다 크다고 가정을 하면 S-G-H-T를 만족하는 T가 주어진 목적지 후보들 중 하나 이상은 존재한다는 뜻입니다.

그러므로 S-H = S-G + G-H를 만족하기 때문에 S에서 H로 가는 최단경로들중 하나는 반드시 G를 지나간다고 생각했습니다.

그래서 두 점 G와 H중 S까지의 최단거리가 더 먼 점 하나만 고려하여 알고리즘을 생각했는데 잘못된 알고리즘인 듯 합니다.

제가 간과한 사실이나 잘못 생각한 부분을 알려주시면 감사하겠습니다.