@tastypotato245
감사합니다 덕분에 풀이할 수 있었습니다.
java로 풀이해서 최단거리 배열을 int에서 long으로 바꿔서 해결했습니다.
그런데, 최솟값은 500*6000*-10,000 으로 -30억이 맞는 것 같은데, 최대값은 499 * 10,000 해서 약 500만이 맞지 않나요? 6천만이 나오는 이유가 뭔지 궁금해서 댓글답니다!
11657번 - 타임머신
@tastypotato245
감사합니다 덕분에 풀이할 수 있었습니다.
java로 풀이해서 최단거리 배열을 int에서 long으로 바꿔서 해결했습니다.
그런데, 최솟값은 500*6000*-10,000 으로 -30억이 맞는 것 같은데, 최대값은 499 * 10,000 해서 약 500만이 맞지 않나요? 6천만이 나오는 이유가 뭔지 궁금해서 댓글답니다!
출력 초과는 아래 예시처럼, 채점해야하는 output의 길이가 다를 때 뜹니다.
answer:
-1
output:
3
4
underflow가 떠서 양수가 됐다면, 마지막 경로를 갱신하는 과정에서 변화가 없게 되어(경로의 코스트가 양수가 되어서, 최솟값이 아니게 되어 갱신을 안하므로), 음의 사이클이 없다고 잘못 판단될 수 있을 것 같습니다.
-30억이 나오는 경우는 이전에 작성 했듯이 500개의 정점이 6000개의 경로를 가지고 코스트 -10,000개를 다 돌면 됩니다. 이 경우 음의 사이클이 무조건 존재하겠죠, 적어도 하나의 정점은 적어도 하나의 간선을 가지게 되고, 500개 중 적어도 하나는 추가의 간선을 가지게 되니까요. (틀렸다면 지적해주세요.)
네 다시보니 약 500만이 맞네요 정점 간 이동에서 모든 간선을 거치면서 가지 않을테니까요. 추가적으로 499 초과의 간선을 갈 필요가 없네요
댓글을 작성하려면 로그인해야 합니다.
tastypotato245 2년 전 34
500개 vertex, 6,000개의 edge가 -10,000 일 경우 최솟값 계산이기에 -30억이 나올 수 있습니다. 양수로는 최대 60,000,000까지만 가능해서 INF값 설정을 작게 잡아도 되지만, dis를 저장하는 배열은 long long으로 선언해야 INT 음수 최댓값 범위 바깥을 커버할 수 있습니다.