파티 C++

[baekjoon 1238] 파티 (플로이드와샬, 다익스트라) (C++)

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 각 집(N)마다 목표점까지 왕복하는 최단 거리 중 가장 큰 값을 찾는 문제이다. 처음에 각 노드 당 최단거리를 구하는 것이기 때문에 플로이드 와샬 알고리즘을 생각했지만, N이 1000으로 O(N^3)의 시간 복잡도를 가지는 플로이드 와샬로 풀리지 않을 것으로 생각했다. 결론적으로는 통과됐다. (왜지?) 플로이드로 풀고, 더 좋은 방법이 없을까 하고 찾아봤더니 다익스트라를 이용해서 ..