naegeora   5달 전

아래 알고리즘 처러 위상정렬순서로 돌면서 각 정점의 earliest 를 구하고, 

역위상 정렬 순서로 돌면서 각 정점의 latest를 구한 후.

각 간선에 대하여

early(x,y)=earliest(x)

late(x,y)=latest(y)-weight(x,y)  구한다.

if(early(x,y)==late(x,y)) 이면 임계경로이다.

아래 로직대로 하면 O(V^2)  2초내로 끝날거 같은데 시간초과 나오네요...

뭐가 잘못된 걸까요? 인접리스트구현을 다르게 해야 하나요?

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