[programmers][2021카카오공채] 합승 택시 요금

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

---

그래프이고 간선에 가중치가 있다. 최단거리알고리즘을 생각해본다.

정점 개수 n의 크기가 200으로 작은 편이므로 플로이드 워셜알고리즘으로 각 정점에서 다른 정점까지 이동할 때 최소 비용을 구해둔다.

pays[u][v] = u->v로 택시를 타고 이동할 때 드는 최소 비용 

 

합승종료지점 m 이라 하자.

이 때, 택시 비용은 출발지점에서 m 위치로 이동하는 비용 + m에서 각자의 집으로 이동하는 비용이 된다.

pays 배열로 표현하면 pays[s][m] + pays[m][a] + pays[m][b] 과 같다.

따라서 m을 0~n으로 두고 위 수식에 적용하여 구한 택시비용들 중 최소 비용이 정답이 된다.

 

시간복잡도는 플로이드 워셜을 사용하여 각 정점 사이 드는 택시 최소 비용 구하는데 가장 오랜 시간이 소요되므로 O(n^3).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/2021%EC%B9%B4%EC%B9%B4%EC%98%A4%EA%B3%B5%EC%B1%84/%ED%95%A9%EC%8A%B9%20%ED%83%9D%EC%8B%9C%20%EC%9A%94%EA%B8%88.cpp

---

적으면서 알았는데 플로이드 워셜 알고리즘에 대한 포스팅을 아직 안했다..

간단히 말하면 중간 지점으로 잡는 정점을 k로 두고 u->v로 이동할때 간선의 최소값을 갱신해나가는 방법이다.

for(k = 0~n){
 for(u = 0~n){
   for(v = 0~n){
      dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
   }
 }
}

참고코드