priority_queue는 Max Heap 구조를 띄고 있어서, 저대로 선언하시면 최소값을 찾아야하는 Dijkstra 알고리즘에선 말 그대로 최장비용 거리를 구하는 알고리즘으로 변해버릴 수 있습니다.

distance값에 음수를 부여해 다시 복구할 때는 음수로 둬서 최소 힙처럼 유지를 하시거나, priority_queue<pair<int, int>, vector<pair<int, int>, greater<pair<int, int>>>로 선언을 변경하세요.

후자의 경우 #include <functional>을 추가해야 정상 동작합니다!

@gallopsys 

답변감사합니다 그런데요
제가 그렇게 해서 해결은 미리했는데요 ㅠㅠ 제가 궁금했던건 저블로그에서의 코드와 거의 다른점이 안보이는데 저 블로그는
시간초과가 나지않고 min_heap과 거의 동등한 속도로 해결이되서 의문이 들어서 질문드렸습니다.ㅠㅠ

@gallopsys

제가 짠 코드에서 pair에 첫번째값과 두번째값이 바뀌어서 그런거같아요
pair의 first값으로 정렬을 하는것같은데 그게 가중치로 되버려서 오래걸렸나봐요 
priority_Heap이 기본구조가 max_Heap이라고 하셨는데 그럼 저 블로그처럼 min heap세팅을 해두지 않으면
기본적으로 max_Heap으로 짜지는거 아닌가요?

네, 말씀하신 것처럼 distance와 to가 달라져서 자동으로 Max Heap처럼 동작해서 그런 듯 합니다만,

아마 Dijkstra 알고리즘이 BFS와 동일한 순회 구조를 보여서 다 일일히 탐색하기 때문에 정확히는 if (cost[p2] < p) continue;에 의해 걸러지는 거라고 볼 수 있습니다.

사실 테스트 케이스를 좀 더 넣어본다면 몰라도 if문에 걸리는 노드가 생각보다 많아서 그런 걸지도 모릅니다.