BOJ 10217 KCM Travel

 

문제 링크 : https://www.acmicpc.net/problem/10217

10217번: KCM Travel

 

지원 비용의 크기가 크지 않아서 각 node(공항) 를 방문했을 때,

다른 비용으로 도달했으면 다른 node 처럼 생각하고 최단 경로를 찾으면 된다.

 

'시간'과 '비용' 두 가지 값을 다루기 때문에 헷갈릴 수 있으니 변수명을 정리하자. 다익스트라 알고리즘을 사용하는데 이중 배열 Dst의 값은 시간이다. 즉, '시간'='거리' 로 처리한다.

 

거리(시간)를 기록하는 distance 배열은

 

Dst[공항][비용] 형태로 사용한다. 예를 들어 Dst[4][5000] 는 4번 공항까지 5000의 비용으로 가는데 걸리는 '시간'이다.

 

이렇게 정의해도 비용의 최댓값이 10,000 이므로, 최대 100x10000 개의 node가 있는 셈이니 대충 풀린다.

Code

Further

지원 비용의 크기가 커졌을 때,  더 좋은 방법이 있는지 고민해 볼 필요가 있어 보인다.