1. 소요 시간이 음수가 되는 경우가 존재합니다. 따라서 다익스트라 알고리즘을 사용할 수 없고 벨만 포드 알고리즘을 사용하셔야 합니다.
2. 시작점(1번 도시)에서 도달할 수 없는 곳에 존재하는 음수 사이클은 신경쓸 필요 없습니다. "1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력"이라고 명시해뒀기 때문입니다. 즉, 도달할 수 있어야 합니다.
3. 벨만 포드 알고리즘을 이용하여 시간을 갱신할 때 (A 도시까지의 시간)과 (B에서 A로 갈 때 소요 시간) + (B 도시까지의 시간)을 비교하는데, 이 때 (B 도시까지의 시간)이 여러분이 처음에 초기화해둔 INF 값인지는 체크해보도록 합시다
4. 자꾸 출력초과가 뜨는 원인은 '1번 도시에서 다른 도시로 가는 길목에 음수 사이클이 존재하는데도 모든 도시로 가는 시간을 굳이 출력'하고 있기 때문입니다. 보통은 아래 둘 중 하나가 원인이므로 꼼꼼히 확인해주세요.
시간의 합이 자료형이 감당할 수 없을 정도로 커지는 경우. Python인 경우에는 정수 간의 연산에서 별도의 제한은 없기 때문에 문제가 되지 않습니다.
INF 값이 충분히 크지 못한 경우. 시간이 매우 걸리는 경로로 가더라도 INF 값을 넘지 못하도록 크게 잡으셔야 합니다. (제가 여기에 걸려서 코드 수정만 계속 했습니다)
ushape 4년 전 10
1. 소요 시간이 음수가 되는 경우가 존재합니다. 따라서 다익스트라 알고리즘을 사용할 수 없고 벨만 포드 알고리즘을 사용하셔야 합니다.
2. 시작점(1번 도시)에서 도달할 수 없는 곳에 존재하는 음수 사이클은 신경쓸 필요 없습니다. "1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력"이라고 명시해뒀기 때문입니다. 즉, 도달할 수 있어야 합니다.
3. 벨만 포드 알고리즘을 이용하여 시간을 갱신할 때 (A 도시까지의 시간)과 (B에서 A로 갈 때 소요 시간) + (B 도시까지의 시간)을 비교하는데, 이 때 (B 도시까지의 시간)이 여러분이 처음에 초기화해둔 INF 값인지는 체크해보도록 합시다
4. 자꾸 출력초과가 뜨는 원인은 '1번 도시에서 다른 도시로 가는 길목에 음수 사이클이 존재하는데도 모든 도시로 가는 시간을 굳이 출력'하고 있기 때문입니다. 보통은 아래 둘 중 하나가 원인이므로 꼼꼼히 확인해주세요.