백준 [BOJ] 10217 : KCM travel

10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 조건이 있는 최단거리를 찾는 문제. 한 도시에서 다른 도시로 가는 최단 거리를 찾는 것이므로 이런 경우에는 다익스트라 알고리즘을 쓰는게 좋다고 알려져있다. 단순 dfs / bfs 를 사용하는 경우는 가중치가 모두 같은 경우이다. 방문했던 곳에서는 다시 탐색을 진행하지 않는 특성 탓이다. 시작점 ~ 방문해야 할 지점까지의 거리를 s라고 하자. 만약 가중치가 다른 상황에서 이미 방문했던 곳을 재방문했다고 해보자 재방문 했을 때 기..

원문링크 : 백준 [BOJ] 10217 : KCM travel