xhdtlsid2   2년 전

82290430번 등 O(NMlogN)풀이가 시간 초과가 나야 합니다.

input

output

khf7000   2년 전

혹시 이 문제를 O(NMlogN) 시간 이외에 풀 수 있는 방법이 있나요?

다익스트라로 최단거리를 구했을 때, 여기에 포함되어 있는 Edge의 개수는 최대 N - 1개이고,

그 N -1개의 경우의 수에 대해서 전부 Dijkstra를 다시 돌려줘야 한다고 생각했습니다..

이렇게 풀면 시간 복잡도가 O(NMlogN)인데, 혹시 여기서 시간을 더 단축시킬 수 있나요??

kcm1700   1년 전

@khf7000 네, NM log N이 느릴 때는 더 빠르게 할 수 있어요.

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