kyaryunha   6년 전

예제 데이터는 양쪽다 잘 출력합니다...!!

왠지 long long.. 이부분이려나요..

아니면 다른 부분이려나요..ㅠㅜ


시간초과 질문합니다..!!


어디서 시간초과가 났을까요??..??..??

starjrm00   6년 전

중간에 모든점에서 다엑스트라를 쓴거는 모든 i,j쌍의 최소거리를 구하는 목적으로 쓰신거같네요.

다엑스트라의 시간복잡도가 O (Elog(V))고, 그걸 V번돌리니 그부분 연산이 상수*(4000*11*2000)번 돌게 됩니다. 계산하면 88000000*상수번 연산을 하게되는데 다엑스트라 내부 상수가 1보다 커보이죠?

아마 저 이유인거 같네요

kyaryunha   6년 전

다익스트라 내부 상수가 1보다 크다는 말이 무슨뜻인지 모르겠어요..!

++ 엥ㅇ 결론은 시간복잡도 터졌다는거려나요..


kyaryunha   6년 전

+ 연산이 1초에 1e9 였나요..? (모름ㅁ)

헉ㄱ 그럼 다른 식으로 풀어야 하나.. 혹시 문제 아신다면 힌트좀 주실 수 있나요??..

starjrm00   6년 전

연산이 1초에 1억번을 돈다고 가정을 하고 문제를 풉니다. (이것도 제가 알기로 10년정도 된 얘기라... K모 사이트의 경우 서버를 바꾸고 3억까지 돌아간다더군요.)

아직 풀어보지는 못했는데 그냥 1번 정점에서 n번 정점까지 가는 다엑스트라를 잘(?) 구현하면 될 듯 합니다.

ps. a++ 등의 연산을 1번이라고 할 때 O(n)은 (임의의 상수)C*n번 연산을 하는 코드라는 뜻입니다. 예를 들어 총 12*n*log(m)번 연산을 하는 코드의 시간복잡도는 O(nlog(m))이 되는 식이죠. (여기서 상수 12는 n또는 m의 크기에 영향을 받지 않아서 표기할때는 무시하게 됩니다.)

다엑스트라 코드를보면 i정점에서 다른 정점과의 거리 비교를 하는 부분만 봐도

int there = adj[here][i].first;
int nextDist = adj[here][i].second+cost;
if(dijk[k][there]>nextDist)
{
    dijk[k][there] = nextDist;
    pq.push({-nextDist,there});
}

(본 코드의 52에서 58번째줄)

여기서 보이는 단순 연산만 2개입니다. (값 대입은 무시하더라도 2번째 줄 +연산, 3번째줄 비교연산, 6번째 줄은 우선순위큐의 처리과정을 생각했을때 대략 O(log(m))정도?)

상수가 3이라 치면 2억 6400만번의 연산을 하게 되서 시간에서 TLE가 나게 됩니다.

(추신이 본문보다 길어보이는건 착각일꺼예요;;)

jh05013   6년 전

그렇지 않습니다.

공식 해법에서도 다익스트라를 V번 돌리라고 되어 있고, 지금 컴퓨터가 그렇게 느리지 않습니다. 

https://www.acmicpc.net/proble...

위 문제에서 식을 세우지 않고 단순 while문을 돌려도 0.5초 정도에 돌아가는 걸 보면 1초에 적어도 20억 번의 연산을 할 수 있습니다.

kyaryunha   6년 전

@starjrm00  근데 그 연산은 최소한으로 필요한(??) 연산 아닌가요?? 어떻게 더 줄여야 할까요..?

@jh05013 헉ㄱ.... 그럼ㅁ 어디서 무한 루프 돌고 잇는 거려나요.... 근데 rand()로 여러번 돌려봐도 무한루프가 뜬적이 없달까요.... (왜지감자..)

kyaryunha   6년 전

처음에 전체 다익스트라 돌리는 것에서  우선순위큐.pop()다음에

            if(dijk[k][here]<cost) continue;


그다음 새로운 다익스트라 돌리는 것에

        if(dist[here]<cost ) continue; 


추가해주니깐 , 5%에서 뜨던 시간초과는 사라지고, 대신 30%에서 메모리초과가 났고,


새로운 다익스트라를 생성하는 부분에서

    tmp = dijk[i][j]*walet[i];     이것을


    tmp = (long long)dijk[i][j]*walet[i]; 이렇게 고쳐주니 해결되었습니다..! 



(( 뭔가 굉장히 기초적인것에서 틀린ㄴ.... (<-기초부진 ㅠㅠ) ))




쨋든 다들 답변해주셔서 감사합니다..! 뭔가 새로운 기초(?)들을 알아갔습니다 :)

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