[C++] 최단 경로, 다익스트라

의문의 시간 초과와의  싸움

 

1753을 다익스트라로 푸는데 endl 대신 \n도 썼고

ios::sync_with_stdio(false);
cin.tie(NULL);

도 사용을 했고

 

중복을 방지하기 위해

if(w>dist[v]) //중복을 방지하기 위해 (시간 단축)
    continue;

도 사용을 했다.

이 부분이 헷갈렸는데 4->5->6 으로 가면 5이고 4->6으로 갈 때 7인 구간이 있다고 해보자

그러면 5을 거쳐 가는게 빠른데 계산을 하다가 4->6으로 가는 7인 구간을 또 거쳐가게 될 수도 있다. 그럴 때 중복을 방지하는 것이다. 당연히 5 만큼에 갈 수 있는 거리인걸 아는데 가중치 7을 가진 간선을 통해 가는 경로는 굳이 탐색해보지 않아도 되는것...

 

이 부분 때문에 시간 초과가 발생하는 다익스트라 문제도 있다고 한다.

그런데 이거까지 다 했는데 왜 시간 초과가 났을까?

 

내가 바보짓을 했기 때문이다~ 

 

priority_queue<pair<int,int>,vector<pair<int, int>>,greater<>> pq;

를 사용해서 가야할 정점과 그 정점까지 가는데의 가중치를 저장을 했다.

우선순위 큐를 사용한 이유는 가장 작은 가중치를 가진 정점을 빠르게 구하기 위해서였다.

greater<>을 사용해서 오름차순을 하면 pair의 첫 번째 요소를 기준으로 정렬이 된다.

 

그래서.. 가중치 순으로 정렬을 하고싶었으면

pq에 (가중치, 정점) 을 넣었어야 했는데 내가 pq에 (정점, 가중치)를 넣어서 시간 초과가 났던 것이다~

 

정신차리자^^

 

같은 실수를 반복하지 않기 위한 기록