티스토리 뷰

공부

Cow Toll Paths (USACO Dec 09 Gold)

구사과 2015. 11. 1. 00:16

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


O(N^4)

Maximum Toll Cost의 경우의 수가 O(N)이니. 이걸 고정시키고 O(N^3) Floyd Warshall을 돌리면 된다. Toll cost T보다 값이 크면 그 근처에 있는 에지들을 몽땅 날려버리고 플로이드. 반복 반복... 시간 복잡도는 O(N^4). TLE다.


O(N^3)

플로이드 와셜의 루프. For(i, j, k) dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);를 생각해 보자.

맨 바깥쪽 루프에서 도는 것은 중간 경유지이다. 2차원 배열에 중간 경유지를 모두 돌면서 업데이트하는 것이다.

그러면, 어떠한 j , k에 대해서, j -> k로 가는 최단 경로가, i까지 경유지가 돌았을 때 i + 1을 경유지로 포함할 수 있을까? 없다.


이제 경유지를 Maximum Toll Cost 증가순으로 올리면서 플로이드 와셜을 돌리면? 각 경유지 마다 현재의 맥시멈 톨비가 정해지니, 아까의 O(N^4) 알고리즘에서 했던 것을 똑같이 할 수 있다. 정점을 끼워넣는다는 식으로 생각하면 편함.

플로이드 와셜의 심오함을 느낄수 있는 문제다. ㄹㅇ 갓고리즘...

'공부' 카테고리의 다른 글

Biconnected Component  (0) 2015.11.10
성적 (USACO Jan 07 Gold)  (0) 2015.11.01
Solving System of Difference Constraints  (3) 2015.10.18
Karger's nondeterministic Algorithm for finding Min-Cut in graph  (3) 2015.10.17
순간이동 장치 (IOI 2008)  (0) 2015.10.15
댓글
댓글쓰기 폼