hun2two   5년 전

다익스트라 알고리즘을 완벽히 구현했는데 틀린 경우 아래 내용 확인

1. INF값을 너무 작게 잡지 않았는지 확인
다익스트라, 플로이드 워셜 알고리즘의 INF = 정점수 * 최대간선비용 +1
→ 이 문제에서는 INF = n*100000+1 하면 됩니다.


2. 문제의 지문에 명시되어 있지는 않지만, 동일 경로에 대해 다른 비용 값이 들어올 수 있음.
이때 최소 비용으로 업데이트 해주는 과정 필요함. 
A->B : 10
A->B : 5


추가로 스페셜 저지 문제이므로 같은 입력에 다른 출력 있을 수 있습니다.
문제 예시는 1-3-5 경로의 cost=4, 1-4-5 경로의 cost=4이므로 둘 중 아무거나 나와도 답임.

댓글을 작성하려면 로그인해야 합니다.