didwlvv   4년 전

다익스트라와 위상정렬을 구현해서 짜봤는데 50퍼에서 시간초과가 뜹니다. 일단 다익스트라 역으로해서 최대값이기 때문에 최대값 갱신일때만 큐를 푸쉬했고 위상정렬은 처음에 시작점을 알기위해서 사용했습니다. 근데 어디가 틀린지 모르겠어요 ㅜㅜ

wonmo   4년 전

p 배열은 해당 정점에 들어오는 엣지의 수를 저장하시도록 사용하셨는데요. 이를 이용해서 현재 보고있는 정점에서 갈 수 있는 정점들의 p배열값을 1씩 낮추면서 이 배열값이 0이 되었을 경우는 0이 된 정점이 이제 더이상 값의 비교를 하지 않으므로 이때 이 정점의 비용은 결정 됩니다. 때문에 p배열의 값을 1씩 낮추면서 0이 되는순간에만 인큐하면 시간을 줄일 수 있구요 한번더 생각하면 목적 정점의 p값이 0이 되는 순간 더이상 루프를 돌지 않아도 됩니다. 아래의 코드로 AC받았습니다.

didwlvv   4년 전

감사합니다 저는 위상정렬로 생각하다가 아닌거같아서 들어가는것만 생각햇는데 읽어보니까 맞네요 ㅎㅎ

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