관련 포스트

https://deepdata.tistory.com/797

시작점은 여러가지 있을 수 있다.

• 지금의 개념을 얻기 전에는 항상 distTable에 대한 생각?
  : 하나의 시작점에서 모든 정점으로 가는 최단 거리가 저장되어 있다고 생각함.

• 여기서 더 나아가자.
  하나의 시작점이 아닌 여러개의 시작점인 경우에도 동일하게 생각해야 한다.
  -> 단 이때의 문제의 조건은 아마도 이럴것이다.

여러개의 spot이 있고, 모든 정점에서 여러개의 spot으로 가는 최단거리를 선택하라.
그리고 문제를 읽어보면, 여러개의 spot을 동일한 입장에서 바라보는
의도가 있다.
: 불특정한 내용

생각해보기

• 여러개의 spot을 시작점으로 본다는 내용에 대해서

• 기존의 다익스트라는 예를 들면
  1번 ~ 5번 정점이 있고, 시작점이 2번이라고 한다면
  2번을 기준으로 해서 1 ~ 5번 정점까지의 최단거리를 구하는 방식이다.

-> 그렇다는 것은 문제에서 a -> b 정점으로 가는 cost가 정해지므로
[a].push_back({b, cost}) 를 하면 된다.

---

• 다시 돌아와서 여러개의 spot가는 경로 중 최단거리를 구하는 것은
  1 ~ 5번 이 spot 3개(가정)로 향하는 간선을 탐색하는 것이다.

• 그렇다는 것은 n개의 정점이 m개의 spot에 대해서 다익스트라를 한다는 것인데

• 다익스트라 시간복잡도는 E Log(n) 이다.
  모든 spot에 대해서 돌려야만 최단 거리를 구할 수 있기 때문에
  E Log(n) * m 이 되어 버린다.

---

접근방법을 달리 하자.

• 이전에는 시작점 1개를 기준으로 모든 정점에 대한 최단거리를
  구하는 것이었기 때문에
  [a].push_back({b,cost}); 였지만,
  지금은 아래의 내용으로 보면, 도시에서 면접장으로 가는 것이 아니라, 면접장에서 도시로 향하는 방법으로 변경해야 한다.

뒤집자.

• spot 을 시작점으로 하고 모든 정점에 대해서 최단거리를 구하는 것과 동일한 방법이다.
  // 조건으로는 반드시 모든 spot 중 최단거리인 정점을 구하는 것이므로, spot 을 별개의 시작점으로 봐야한다는 것이다.
  -> 그렇다는 것은 굳이 위의 방법처럼 spot 하나를 찾기 위해서
  다익스트라 1회 * spot m번 만큼 할 필요 없다.

• 이러한 생각이 가능한 이유는
  : 모든 정점에서 여러개의 spot 가운데서 가장 가까운 spot 과의 최단거리를 구하라는 것이므로,
  dist 테이블에 그냥 가장 가까운 dist만 넣기만 하면 된다.

• 코드
  1) vertex 삽입 시 뒤집어야 한다. 시작점을 spot으로 하기로 했으니,[b].push_back({a , cost}) 로 가야 한다.
  -> 왜냐하면 기존에 vertex 주어질때 a 정점에서 b정점까지로
  가는 간선인데, 우리는 반대로 면접장에서 도시로 가는 것으로 변경했기 때문이다.
  

2) pq 에 시작점이 여러개인 spot을 전부 넣어놓고, 다익스트라 진행하자.

• 관련 문제
  : 17835 면접 보는 승범이네
  : 14221 편의점.