문제 해결 전략

• 다익스트라.
• 우선순위 큐

왜 틀렸을까?

• 모든 정점의 dist 중에서 k번째의 최단거리를 구하는 문제이다.

• 오름차순 순으로 하고 있다.
  : k는 2이고,
  2번 정점을 path TAble은 2 15 19, 10 등등이 있다.
  매번 dist[2].push_back 할 때마다 데이터를 넣어주는데,

• 오름차순이기 때문에 가장 낮은 친구가 어쨋든 dist[2] 컨테이너에서 0번째에 와야 한다.

• 그러다가 이게 path 의 Count가 dist.size() > k 가 되는 순간이 발생할 수 있따.

• 뒤죽 박죽 되어 있는 dist[2] 과 newPathDist 를 비교해서
  그냥 dist[2]에다가 넣어야 하는 것인가??? 를 생각해보았다.

• 2 15 19, 10 , 7, 11을 넣는다고 하자. 그런데 k는 2라고 할 때 , 어떻게 했을 때
  -> 2번째 최단거리를 얻을 수 있을까? 생각해보면

• 미지의 컨테이너에 2를 넣고, 15를 넣었다. (15는 size가 1이므로 넣을 수 있따.)
  그런데 19를 넣으려고 하는데, k번째 이므로 컨테이너의 가장 큰값인 15와 비교 하면 된다. 15보다 크므로 넣을 필요 없다.

• 2 , 15 vs 10
  -> 15보다 작으므로 넣어도 된다.

전략

-> 즉 distTable을 pq로 관리하면서 가장 큰값이 top에 오게 설계 해서 관리하자.

결론

: 오름차순 정렬되어 있는 컨테이너에서 k번째 위치한 데이터를
뽑아라고 한다면, priority_queue를 생각할 수 있따.