2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금

이 문제는 택시비를 간선 간의 거리로 보면 그래프 상에서 최단거리를 구하는 문제로 생각해 볼 수 있다. 주요 포인트는 두 사람 A와 B가 합승을 통해 전체 비용을 단축시킬 수 있다는 것이다. 최소비용으로 A와 B 각자의 목적지에 갈 수 있는 경우는 두 가지 경우로 나눠볼 수 있다. 합승해서 같이 임의 지점까지 최단 비용으로 이동한 후, 여기서 각자의 목적지를 향해 최단 비용으로 가기 합승을 하지 않고 시작점 s에서 각자의 목적지를 향해 최단 비용으로 가기 두 가지 경우의 비용을 비교해서 더 작은 비용이 답이 될 것이다. 1번 방법의 최소 비용을 구하기 위해서는 시작점 s에서 임의의 지점까지 가는 최소 비용과 함께, 이 지점에서 각자의 목적지까지 가는 최소비용이 필요하다. 마침 지점의 갯수 n의 최대값도 ..