문제풀이

최단거리 문제로 모든 간선에 대해 막는다 생각하고 다익스트라를 돌린다면
M(N+MlogN)이 나올 것이다. M 개의 간선 * (N 개의 정점 초기화 + 다익스트라)
사실 생각해 보면 최단거리에 포함되지 않는 간선은 막을 필요가 없다.
어차피 그쪽으로 가지 않기 때문이다. 그렇다면 우리는 최단거리를 구한 뒤
최단거리를 역추적하여 경로를 구할 수 있다.
그 후 역추적한 경로의 간선들만 사용하지 못하게 하여 다익스트라를 돌려주면 해결할 수 있다.

코드

solution

문제링크

boj/2307