na982   4년 전

입력 받은 시작점으로 다익스트라를 돌리고,  g, h, lst_t노드들의 최단거리값을 저장하고 있다가,


g 를 시작점으로 다시 다익스트라를 돌려서, 전에 구한 s->g의 값과 g를 시작으로 t노드들에 도착하는 결과를 더한 값과 s->t를  비교해서 같은 값이면 정답 리스트에 넣고,

(s->g + g->t == s-t 라면 정답 리스트.)

h를 시작점으로 다시 다익스트라를 돌려서, 전에 구한 s-h 의 값과 h를 시작으로 t노드들에 도착하는 결과를 더한 값과 s->t 를 비교해서 같은 값은 값이면 정답 리스트에 넣습니다.

(s->h + h->t == s-t 라면 정답 리스트.)


위과정으로 하면 정답이 나와야 할것같은데;; 잘 안나오네요; 어디가 잘못된걸까요?

na982   4년 전

g 또는 h 지점중 시작점에서 먼점인 경우만 처리 해줘야 맞는 솔루션 이네요;;


jh05013   4년 전

s->g, g->h, h->t로 가야 합니다. g까지 가 놓고 정작 gh 간선을 타지 않을 수도 있으니까요.

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