tastypotato245   2년 전

500개 vertex, 6,000개의 edge가 -10,000 일 경우 최솟값 계산이기에 -30억이 나올 수 있습니다. 양수로는 최대 60,000,000까지만 가능해서 INF값 설정을 작게 잡아도 되지만, dis를 저장하는 배열은 long long으로 선언해야 INT 음수 최댓값 범위 바깥을 커버할 수 있습니다.

kangsm423   2년 전

@tastypotato245
감사합니다 덕분에 풀이할 수 있었습니다.
java로 풀이해서 최단거리 배열을 int에서 long으로 바꿔서 해결했습니다.

그런데, 최솟값은 500*6000*-10,000 으로 -30억이 맞는 것 같은데, 최대값은 499 * 10,000 해서 약 500만이 맞지 않나요? 6천만이 나오는 이유가 뭔지 궁금해서 댓글답니다!

ehdrjs233   2년 전

갑사합니다 감사합니다 감사합니다 감사합니다 감사합니다

bjh7536   2년 전

감사합니다. 그 생각을 못했군요. 입력 값 범위를 신중히 고려하는 것도 습관을 들여야겠습니다.

lsnan421   2년 전

감사합니다. 덕분에 해답 얻고 갑니다.

shyou1119   1년 전

출력초과가 underflow가 발생하면 나오는건가요? 그리고 -30억이 나오는 경우가 음의 사이클이 존재하는 조건에서 말씀하시는 건지?

tastypotato245   1년 전

@shyou1119

출력 초과는 아래 예시처럼, 채점해야하는 output의 길이가 다를 때 뜹니다.

answer:

-1

output:

3

4

underflow가 떠서 양수가 됐다면, 마지막 경로를 갱신하는 과정에서 변화가 없게 되어(경로의 코스트가 양수가 되어서, 최솟값이 아니게 되어 갱신을 안하므로), 음의 사이클이 없다고 잘못 판단될 수 있을 것 같습니다.

-30억이 나오는 경우는 이전에 작성 했듯이 500개의 정점이 6000개의 경로를 가지고 코스트 -10,000개를 다 돌면 됩니다. 이 경우 음의 사이클이 무조건 존재하겠죠, 적어도 하나의 정점은 적어도 하나의 간선을 가지게 되고, 500개 중 적어도 하나는 추가의 간선을 가지게 되니까요. (틀렸다면 지적해주세요.)

tastypotato245   1년 전

@kangsm423

네 다시보니 약 500만이 맞네요 정점 간 이동에서 모든 간선을 거치면서 가지 않을테니까요. 추가적으로 499 초과의 간선을 갈 필요가 없네요

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