[BOJ] 2398번: Conference Call

https://www.acmicpc.net/problem/2398

세 스위치를 s1, s2, s3이라고 합시다. s1에서 s2로 가는 route와 s1에서 s3으로 가는 route에는 반드시 마지막으로 갈라지는 switch가 존재합니다. 그러니 dist[s1][t]+dist[s2][t]+dist[s3][t]가 최소가 되는 t를 구하고 s1 -> t, s2 -> t, s3 -> t의 최단 경로 상에 있는 line만 있으면 최소 비용으로 통신이 가능합니다. 이러한 t와 t에 대한 line은 플로이드 와샬 알고리즘으로 구할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/2398.cpp