'다익스트라 알고리즘'이 추가되어야 한다고 생각합니다.

K가 최대 10,000이고 도시 숫자 N이 최대 100, 도로 개수 R이 최대 10,000이어서

현재 정점 번호 + 소지금 2개 정보를 가진 O(NK)개 정점으로 다익스트라 알고리즘을 사용하여

O(E + VlogV)의 시간복잡도로 무난하게 제한시간 안에 문제를 풀 수 있는 것으로 보입니다.

naive한 간선 개수로 보이는 O(RK)가 굉장히 큰 값이지만 실제로는 이보다 훨씬 적은 개수의 간선이 존재하여 문제가 풀리는 것 같네요.

실제로 랭킹의 상위권이신 분들 소스 코드가 전부 다익스트라 알고리즘을 사용하고 있습니다.