[BOJ] 10217번: KCM Travel

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

1. $D[i][j]$를 1번 도시에서 $i$번 도시까지 비용 $j$ 이하를 써서 갈 때의 최소 시간이라고 한다면, 이 $D$ 테이블을 차례대로 모든 교통편($K$개)를 확인하면서 채워나가면 됩니다. 시간복잡도는 $O(MNK)$입니다. 100억이라 애매할수도 있지 않나 싶었는데 꽤 빨리 돌아갑니다.

2. $D[i][j]$를 1번 도시에서 $i$번 도시까지 정확하게 비용 $j$를 써서 갈 때의 최소 시간이라고 한다면, 다익스트라 알고리즘에서 시간이 낮은 순으로 원소를 priority queue에서 뽑아내게끔 해서 해결할 수 있습니다. 시간복잡도는 $O(KM*log(NM))$인 것 같습니다.(확실하지는 않습니다. 많이 헷갈리네요 ㅠ_ㅠ) 구현 난이도도 1번보다 높고 실제로 돌렸을 때 걸리는 시간도 1번보다 깁니다. 저는 2번 방식으로 짰는데 정답자들의 코드를 살펴보다가 1번 방법도 가능함을 깨달았습니다.

https://github.com/blisstoner/BOJ/blob/master/10217.cpp