image.png

문제 풀이

다익스트라 알고리즘의 새로운 간선의 가중치를 더하는 부분을 곱하기로 바꿔주면 된다. 이 때 우선순위 큐의 초기값으로 0이 아닌 1 또는 -1을 넣어줘야 하는 것을 주의 해야 한다. 초기값이 0이 아니라 노이즈가 없는 경우 1이기 때문이다.

느낀점

복잡한 소수점 계산의 경우 long double 형을 사용할 수 있다. 이 때 서식 문자는 Lf이다. double 형의 max 값은 DBL_MAX를 사용한다. 문제 해결 과정 중에 큰 수가 나올 경우를 대비해 99999...와 같이 쓰는 것보다 DBL_MAX를 쓰는 것이 좋다.