https://www.acmicpc.net/problem/25050
문제요약
- (S,E) 최단경로 사용되는 간선에 +1
- 모든 (S,E)에 대해서 처리
- 가장 높은 점수 간선들 출력
- 최단경로가 존재한다면 한가지 경우만 존재
- 노드 2000, 간선 5000
접근법
- 모든 (S,E)의 최단경로를 구해야하는데 플로이드-와샬은 안됨
- 다익스트라를 사용한다면
- 모든 S에 대해 수행
- 다익스트라 시간 복잡도 O(ElogE)
- 전체 복잡도는 O(VElogE) : 2000500013 = 1.3억
- 다익스트라를 통해서 최단경로에 사용한 간선을 구하고
- 사용한 간선만으로 그래프를 구성하고
- 자식의 수만큼 해당 간선을 최단경로에서 사용했다고 처리함(해당 간선을 이용해 몇개의 목적지를 갈 수 있는지로 생각하면 됨)
다익스트라 시간 복잡도
- 매번 헷갈려서 정리를 좀 해보면
- 어떤 노드의 인접한 간선에 대해서 거리 비교 작업을 수행 : V처럼 보이지만 인접한 간선만큼 다 수행을 해야하므로 E
- 비교작업은 값을 갱신할 수 있을 때 우선순위 큐에 넣는 작업 : 우선순위큐에 들어간 양 = 갱신되는 만큼 = E
- 그래서 O(ElogE)로 볼 수 있는데 E=V^2가 지배적이라 O(ElogV)로 본다고 함
newbieski