플로이드2 [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 배열을 탐색하면.. 2019. 3. 4. [BOJ][1504] 특정한 최단 경로 문제 : https://www.acmicpc.net/problem/1504 최단거리를 구하는 문제이다.플로이드 알고리즘으로 먼저 모든 정점 간의 최단 거리를 구한다.1 -> N 까지 이동하는데 반드시 지나야 하는 지점 2개가 a, b라면나올 수 있는 경로는 1 -> ... -> a -> ... -> b -> ... -> N1 -> ... -> b -> ... -> a -> ... -> N위 경로 2개이다. 따라서 1 -> a 최단 거리 + a -> b 최단거리 + b -> N 최단거리1 -> b 최단 거리 + b -> a 최단거리 + a -> N 최단거리위 2개 중 짧은 거리가 정답이 된다.만약 구한 짧은 거리가 무한대라면 불가능한 경우이므로 -1을 출력한다. 소스코드 : https://gist.gith.. 2019. 1. 27. 이전 1 다음