목록2025/03/06 (1)

공부 흔적남기기

[JAVA] 파티 1238

문제는 각 지점에서 X까지의 최단거리 + X에서 각 지점까지의 최단거리이다. 최단거리 문제를 해결하기 위해서 다익스트라, 벨만, 플로이드 워셜을 고려해볼 수 있는데일단 음수 사이클이 존재하지 않으므로 다익스트라와, 플로이드 워셜을 고민해보았고, 처음에는 모든 정점에서의 거리가 필요할 것 같아서 플로이드 워셜인가 싶었지만,플로이드워셜의 시간복잡도 O(V^3) 1000^3 이라 10억 불가..다익스트라로 해결할 경우 V(logV)E 100 * 8 * 10000 800만 -> 시간복잡도상 더 빠를 것 같고 다익스트라가 손에 더 익숙하기 떄문에 다익스트라로 결정 문제로 넘어와서 dist[][]를 만들고 각점들마다 최단거리를 다 구하고 dist[i][x] + dist[x][i]의 최대값을 구하면 끝나는 문제 im..
코테/백준 2025. 3. 6. 23:08
이전 Prev 1 Next 다음