qkdtmdeh   6년 전

안녕하세요. 임계 경로 문제를 푸는데 오전내내 고통받다가 질문 올려봅니다.

사이클이 없는 단방향그래프이기에 모든 간선 cost를 -1곱하여 최단경로를 구한후 그값을 dist배열에 저장해서 bfs를 돌리면서

최단경로에 이용되는 간선들을 세어주는 방식으로 해서 답을 낼 때에는 dist값에 -1을 곱하여 계산했는데요.

논리에 오류가있나요??

zasxer   6년 전

이게 문제일지는 모르겠지만

Screenshot_20170526-155206.jpg


qkdtmdeh   6년 전

엇!! 안녕하세요. ㅎㅎ 저 글씨로 쓰신게 모든 간선의 코스트가 1일때를 의미하는 건가요?? 마지막에 9000*1000의 뜻을 잘 모르겠습니다. 간선의 갯수를 저렇게 헤아리게 된다는 뜻인가요??

zasxer   6년 전

저런 구조의 Graph 라면 큐에 900만개가 쌓인다는 말

qkdtmdeh   6년 전

아;;;;; 큐뻑이난다는 뜻이군요. 헐 그러면 아예 다른방식으로 짜야되는건가요..??

zasxer   6년 전

spfa까지는 맞는 거 같고 아래 거 생각을 좀 더 하면 될듯

qkdtmdeh   6년 전

그런데, 생각해보니깐 2500만개정도까지도 들어올것같은데,,, 이거 배열뻑 안나게 할수있는 방법이 있나요? 역추적 방식을 다르게 해야하나;;

qkdtmdeh   6년 전

흐흠 좀더 생각을 해봐야겠네요. ㅎㅎ 시간내주셔서 감사해요.

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