문제풀이

다익스트라 문제로 K 개의 도시를 제외한 N-K 개의 도시를 출발 정점으로 모두 다익스트라를 돌려주면 당연히 시간 초과가 발생한다. 발상의 전환이 필요한 문제이다. 결국 특정 정점에서 K 정점으로 가는 최단거리는 K 정점에서의 최단거리라고 볼 수 있다.(단방향이기 때문에 간선을 뒤집어야 함) 그렇다면 모든 K 정점에서 다익스트라를 돌리면 될까? K(1 ≤ K ≤ N) 이러한 조건 때문에 불가능이다.
그렇기에 모든 K 개의 정점과 가중치가 0인 간선으로 연결된 하나의 정점을 만들어주고 그 정점에서의 최단거리를 구해주면 답을 얻을 수 있다.

코드

solution

문제링크

boj/17835