[PRGRMS]72413번: 합승 택시 요금

문제: https://programmers.co.kr/learn/courses/30/lessons/72413

---

플로이드 문제입니다.

 

최저 택시 요금 후보로 갈 수 있는 경로는 크게 4가지입니다.

 

1. A를 경유해서 가는 경우: S => A => B

2. B를 경유해서 가는 경우: S => B => A

3. 각 각 택시를 타는 경우: S=> A + S => B

4. S와 A, B 사이에 임의의 경유지 i를 두는 경우(첫 번째 테스트 케이스): S => i + i => A + i => B

 

플로이드로 모든 경로쌍을 구한 뒤에 위 4가지 경우를 계산하여 최소값을 리턴하면 됩니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%ED%95%A9%EC%8A%B9%20%ED%83%9D%EC%8B%9C%20%EC%9A%94%EA%B8%88.java​