Cow Toll Paths (USACO Dec 09 Gold)

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) 알고리즘에서 했던 것을 똑같이 할 수 있다. 정점을 끼워넣는다는 식으로 생각하면 편함.

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