mellllon   2년 전

이 코드에 따르면 

47번 줄에 우선순위큐에 다음 릴렉스 할 위치와 cost를 넣을 때

pq.push(make_pair(nthere,ncost)); 로 구현되어있습니다.

그런데 제가 알기로는 우선순위 큐에 pair(a,b)를 넣으면 

a를 우선적으로 비교하여 정렬하고, a가 같으면 b를 비교하여 정렬하는 것으로 알고있는데

저 코드대로라면 한 지점에서 릴렉스를 수행 한 뒤 다음 릴렉스할 장소를 최소 cost의 장소에서 하는 것이 아닌

단순히 꼭지점의 index 번호를 기준으로 수행하여 릴렉스 횟수를 늘리고 불필요한 연산을 하게 되는것 아닌가요?? 

이런 경우에 불필요하게 여러번 빙글빙글 도는거 같은데

4 6 1 

1 3 20 

1 2 9 

3 2 2 

2 3 1 

2 4 6 

3 4 3

왜 이 코드가 정답으로 나오는지 모르겠습니다

startlink   2년 전

Dijkstra 알고리즘

epikem   2년 전

정말이네요. 게다가 first second 순서를 바꿔서 cost를 기준으로 하면 오히려 시간초과가 나네요.

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