[CodeJam][2017][Round 1B] C. Pony Express

문제 : https://code.google.com/codejam/contest/8294486/dashboard#s=p2&a=1

---

참고 : http://kmjp.hatenablog.jp/entry/2017/04/24/1000

위 포스팅을 보고 풀었다.

입력

N : 말을 가진 도시의 수

Q : 흥미있어하는 정착지 개수

N개의 Ei(i번째 말로 갈 수 있는 최대 거리. kilometers), Si(속도. k/s)

NxN의 Dij(i -> j 거리)

Q개의 Uk(시작 위치), Vk(종료 위치)

출력

Q개의 Uk -> Vk로 가는 최소 시간. 

플로이드 워셜 알고리즘을 2번 돌려서 풀었다.

먼저 입력받은 D 배열(거리)로 i -> j로 가는 최단 거리를 플로이드를 돌려서 구한다. (O(N^3))

D를 구했으면 D 배열을 탐색하면서 i -> j로 갈 때, i 번째 말을 이용해서 이동 했을 때의 시간을 구한다. (O(N^2))

입력에서 속도(Si)를 입력 받았으므로 D[i][j] / S[i] 가 구하고자 하는 시간이 된다. (거리 = 시간 X 속도)

이 때, i번째 말로 이동할 수 있는 최대 거리 제한이 있으므로 D[i][j]와 E[i]를 비교하여 말로 이동할 수 없는 경우는 예외처리해준다.

시간 배열을 만들었으면 이 배열로 다시 한 번 플로이드를 돌리면서 각 지점으로 이동했을 때의 최소 시간을 구할 수 있다.(O(N^3))

만든 최단 시간 배열로 Q개의 Ui -> Vj 로 가는 최소 시간을 구할 수 있다. (최단 시간 배열[i][j])

시간 복잡도는 O(N^3).

N이 최대 100이므로 가능하다.

---

소스코드 : https://gist.github.com/fpdjsns/25006d98d8c5f876468ddaf105b5957c