[백준 1753] 최단경로

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

 

다익스트라 알고리즘 문제입니다. 

일단 그래프를 인접행렬로 구현하게 되면 메모리 초과가 발생할거 같아 ( 정점 최대 갯수 20000 )

인접 리스트로 구현했습니다.

처음에는 그냥 우선순위큐에 다음 위치 ( Integer로) 를 저장해 쓰다가 시간초과를 바로 먹었습니다. 

(원래 매 루프마다 방문하지 않은 정점 중 시작점으로 부터 가장 가까운 정점을 뽑는게 당연함. 안해서 빠꾸먹음)

 

Comparator를 하나 만들어 거리가 가장 가까운 녀석이 높은 우선순위를 가질 수 있도록 합니다.

 

while문의 변수 이름들이 상당히 지저분한데 우선순위 큐의 제너릭이 Integer에서 NextNode로 변했기 때문에 

대충 고쳐서 통과만 시켰지만 보기엔 좀...