백준 1753. 최단경로

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

다익스트라 알고리즘.

지금까지 푼 다익스트라 문제들은 무방향 그래프였는데 방향 그래프여도 똑같이 풀면된다. 

근데 계속 시간초과, 수정하면 메모리 초과가 났는데 지금까지 다익스트라 알고리즘을 살짝 잘못 쓰고 있었다.

우선순위큐에 넣는 과정에서, 인접 노드 중 가중치 작은 노드부터 방문해야 하므로 우선순위 큐에 pair의 first로 거리값을 넣어야 거리 기준 정렬이 되는데 (-를 붙여서 내림차순으로), 지금까지 second로 거리값을 저장했었다.

그런데 지금까지는 문제들은 정점의 갯수가 그렇게 많지 않아서 별 문제없이 통과했나보다.