chogahui05   2년 전

그리디로 접근이 가능할 거 같아서 이렇게 풀어 보았습니다. (채점번호 5131838)


(1) i부터 j까지의 최단거리를 차례로 입력받습니다. 

이 중, i에서 j까지 가는 최단 cost에 대한 정보를, (cost가 최소인 게 우선순위가 높은) 큐에 넣습니다. (단 i<j)


(2) 우선 순위 큐에서 아이템을 뺍니다. 이것을 test라고 합니다.


(3) test에는 출발지와, 도착지가 있습니다. 그리고 cost가 있습니다.

기존에 알려진 비용보다, 큐에서 뺀 새로운 정보인, 출발지에서 도착지로 가는 정보가 더 짧다면 꼭 있어야 하는 길이기 때문에

  = path 벡터에 넣습니다.

  = from에서 to까지의 경로를 새로 추가해서, x에서 y까지의 경로를 업데이트 합니다.


(4) (2)와 (3)을 큐가 빌 때 까지 계속 반복합니다.

 

(5) 이 과정을 통해서 만들어진 최단 거리 배열이 nc입니다.

기존에 알려진 건 total_cost입니다. 이 둘의 배열을 비교한 후에 다르다면 -1를 출력하고 종료합니다.


플로이드로는 접근이 잘 안 되길래.. 그리디로 풀어본 건데요.

플로이드로는 어떻게 접근을 하면 좋을까요? 감이 잘 안 옵니다.. ㅠㅠ

disy   2년 전

플로이드는  dist[i][j] 값과 어떤 k 를 거칠 때 의 dist[i][k]+dist[k][j] 값이 같다면  i->j 와 i->k->j 이므로 i->j 간선이 필요 없어지는 것을 이용합니다.

chogahui05   2년 전

최단거리가 갱신될 때 조건이라.. 음..


그러니까 i->j가 필요 없어지는 경우가.

어떠한 k를 거칠 때 i->k, k->j를 거치는 경우가 i->j로 바로 가는 경우보다 (짧거나) 같다면 굳이 i->j가 있을 필요가 없고..

k를 거쳐야 하는 경우도 i에서 j를 거쳐가는 게 더 크니까.. 음..


조금 더 연구를 해 봐야겠네요.. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.