문제 링크: https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 www.acmicpc.net 다익스트라, DP 알고리즘 j의 비용을 사용해서 i번 정점까지의 최단 거리를 저장할 2차원 DP[i][j] 배열을 만들고 다익스트라 알고리즘을 사용하면 됩니다. 최단 거리를 구할 때 2가지 최적화 방법을 적용할 수 있습니다. 1. 정점 u를 비용 c로 방문하여 최단 거리를 갱신할 때, 비용 c보다 큰 비용으로 정점 u를 방문하는 경우는 고려하지 ..