문제 및 풀이

풀이 어려웠던 요인

최단 경로의 path가 아래 2가지 갈래로 생길 수 있음을 예상하기 익숙치 않았다.
1. 최단 경로가 여러 개 있을 수 있음. 예제에서 확인 가능
2. 최단 경로의 path가 2개 이상의 갈래가 한 곳으로 모이는 경우가 있음. 이 경우도 제거하기 위해 vector<int> pathsToMe 형태로 만들어주어야 했다.
첫번째 탐색 이후 edge를 inValid하게 만든 후 두번째 탐색으로 답을 구하고자 했다. 이 탐색을 빠르게 하려면 처음에 주어지는 edges 정보를 평소에 하던 방식처럼 edges[s].push_back({ d, dist, true }); 형태로 초기화하면 이후 invalid하게 만들기 위해 true를 false로 변경이 필요할 때에 임의 edges에서 반복문 탐색하며 찾아야 하는 문제가 있었다. → 입력을 그대로 갖는 edges 배열을 쓰고, 여기에 bool isValid 멤버 변수도 두고, 기존의 edges는 vector<int>edgeIndices[s] 로 변경한다. 그러면 임의의 start node가 edge index를 참조하고 있어서 기존의 pathsToMe도 vector<int> edgeIndicesToMe 로 갱신해서 다익스트라 탐색은 동일하게, 최단 경로 edge 제거 연산도 $O(M)$으로 빠르게 가능했다.

다익스트라를 N번 해서 답을 구했으나, 더욱 최적해는 플로이드-워셜 알고리즘을 사용한다.

플로이드 워셜 알고리즘을 통한 더 최적화된 풀이는 여기로