[프로그래머스] 합승 택시 요금 C++

코딩테스트 연습 - 합승 택시 요금 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지 는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다. 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택... programmers.co.kr 정점들 간의 최소 거리를 구해주기 위해서 플로이드 와샬 알고리즘을 이용했다. 문제에서 가장 핵심이 되는 부분은 어떤 경유지를 선택 해야될까이다. 역시나 가장 간단한 방법은 모든 정점을 경유지로 선택해서 요금을 계산하고 최솟값을 구해주면 된다. 플로이드 와샬로 먼저 정점 간의 최소 거...

원문링크 : [프로그래머스] 합승 택시 요금 C++