Level3 (kakao) 합승 택시 요금

https://programmers.co.kr/learn/courses/30/lessons/724131. 다익스트라 풀이 2. 플루이드 와샬 풀이필요한 로직 : 다익스트라 or 플루이드 와샬[배경]시간 제한이 넉넉했는지 플루이드 와샬 풀이도 가능했다. 정점 간 정보를 모두 담고 간다는 면에서 플루이드 와샬 풀이도 편하지만, "경유지"의 개념을 도입해 다익스트라로 풀어도 유익하다.[논리]모든 가능한 경유지 t에 대해서 min(s->t + t->a + t->b)를 활용한다. 이 경우 그림에서 보듯 A와 B가 합승한 뒤 독립적인 path를 가거나, 합승하지 않거나, A나 B가 한 노드의 path 안에 속할 경우 모두를 함축할 수 있다. 다익스트라를 세번 돌려 dist table을 stable..........

원문링크 : Level3 (kakao) 합승 택시 요금