니가 이해하기론 5랑 연결된게 3->5랑 4->5가 있고 최단경로는 1->3->5인데


3->5의 가중치는 3이고 4->5의 가중치는 1이면 p[5]는 4가 되는거고


이 때, 4 이전에 연결된 점이 없을 수도 있다. 이 말 아님?


이해를 잘못한듯 한데 무조건 도착지점에서 역순으로 가서 최단거리를 넣으라는 말이 아니야


다익스트라 돌아가면 기존 경로랑 새로 탐색한 경로를 비교하지?


그 때 새 경로가 더 빠른 경로라면 그 때 array값을 바꾸라는 거임.


즉 최단 경로로 발견한 놈이 n이라면 n 이전의 노드, 즉 부모의 값을 array에다가 넣으라는거임


경로가 1->3이라면 새로 찾은 놈은 3이고 걔의 부모는 1이겠지? 그러면 p[3] = 1 이런식으로





그리고 경로 그렇게 n*n array에 넣으면 time complexity O(n^2) 나오니까 priority queue랑 graph를 쓰자