[1238] 파티

다익스트라를 사용하여 간단하게 해결 가능한 문제이다.
기본적으로 다익스트라는 한 지점에서 다른지점까지의 최단 거리를 구하는 방법이다.
여기서 문제는 특정도시 X로 간 후 다시 자신의 위치로 돌아오는 것이 이 문제의 핵심이라 생각한다.

Sol)

1. 각 도시마다 다익스트라를 이용해 목적지 도시 X 로가는 최단 시간을 구한다.
2. X에서 모든 도시로 가는 최단 시간을 다익스트라를 이용해 구한다.
3. X로 간 후 다시 돌아오는 시간을 더하여 최댓값을 구한다.

어렵게 시간복잡도를 생각하여 구하기보다 일단 해보면서 해결책을 강구하는 것이 더 빠르게 풀 수 있는 방법이란 것을 느꼇다. 모든 길을 구하는 것이기 때문에 플루이드 워셜 알고리즘을 이용해야하나? 하면서도 N이 1000이어서 시간초과가 날까 하여 할까 말까 많이 망설였기 때문이다.