cartoonman   3달 전

다익스트라로 구현해봤고, 다익스트라에서 최소값 뽑는걸 힙 이용하면 더 빨라진다해서 힙으로 구현해봤습니다.

일단 x에서 각 마을로 가는 시간을 구해서 weight라는 배열에 복사해두구

한명씩 x에 가는 최소 시간을 구합니다. 그다음 weight 해당 인덱스의 값과 합쳐서 최대값 비교하여 출력.. 하는데요

n명을 각각 다익스트라를 다 돌리다보니까 시간 초과가 난다고 생각이 듭니다.. 이거 어떻게 더 줄일 수 있을까요

sksdong1   3달 전

2번의 다익스트라로 해결할 수 있습니다.

목적지를 시작점으로 돌리면 각 마을로 가는 최단거리를 한번만에 얻을 수 있죠,

하지만 단방향 도로이기 때문에 N개의 마을에서 목적지로 오는 경로는 다르게 되므로 

역방향의 그래프를 하나더 만들어서 목적지에서 다익스트라 돌리면 마을에서 목적지로 오는 최단거리도 1번에 구할 수 있어요

cartoonman   3달 전

감사합니다. 성공했습니다.

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