meme0724   1년 전

비주얼 스투디오에서는 제대로 실행이 되는데

여기서 채점을 하려고 하면은 런타임 에러가 뜨네요

무슨 문제가 있는건가요?

pichulia   1년 전

일단 런타임 에러가 발생한 원인은 배열 인덱스 초과때문입니다.

지금 보시면 chk배열을 chk[20001] 으로 잡았는데 20000보다 더 큰 i로 chk[i]를 접근하려 하고있습니다.

어디서 일까요?

for (i = 1; i <= v; i++)

{

if (chk[i] == 0 && big.first >= dis[i])

{

big.first = dis[i];

big.second = i;

}

}


이 부분인데요..

엥? 1≤V≤20,000 니까 안전범위 아니냐고요?



저 for문의 v값이 어디서 왔는지를 추적해봅시다


void dij(int k, int v)

이렇게 dij 함수 인자로 v를 사용하고 있는데

int main()

{

...

dij(k, e);

...

return 0;

}


main 함수에서 저 v에 대응하는 값으로 e를 넘겨주고 있습니다.

e값의 범위는 1≤E≤300,000 이므로

dij 함수에서 사용하는 v변수의 값의 범위도 1≤v≤300,000 이고,

따라서 i가 300,000까지 커질 수 있게 됩니다....ㄷㄷ


그러니 일단

void dij(int k) 로 바꾸고,

while문 안의 첫번째 for문을 i=1 ~ e 로 바꿔봅시다.

그럼 안정적으로 시간초과를 받으실 수 있답니다. (???)


어디가 또 문제인지는....음...일단 힌트를 드리면

while(s != v) 아래로 한 3줄 정도를 고칠 필요가 있네요



pichulia   1년 전

이런... 한두줄 정도 바꾸는걸로는 시간초과가 해결되지 않네요...

O((V+E)logV) 짜리 다익스트라 알고리즘에 대해 공부해봅시다.

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