mrcamel   1년 전

go(cur, prvi)가 호출되면

(cur로 올 수 있는 방법) x (cur에서 prvi로 갈 수 있는 방법)

을 리턴해주는 방식으로 만들었습니다.


예로 도착지가 4일 때

1->3, 1->2->3으로 오는 방법이 (4,3), (3,2)고 3->4 가 (1,2) 일때

1->4로 올 수 있는 방법은 (4 + 1, 3 + 2), (3 + 1, 2 + 2)입니다


직접 데이터도 몇개 만들어보고 몇시간 고민 해봤는데 잘 안풀립니다..

다른 분들은 소스 저보다 엄청 짧으신데 제가 괜히 복잡한 방향으로 생각한 것 같네요;

도움 주시면 정말 감사하겠습니다.

appa   1년 전

D(i, j) : i번째 도시를 방문할 때까지 j만큼의 비용을 사용했을 때, 가능한 최소 소요시간으로 table을 정의해서 O(E log E) 다익스트라와 동적계획법을 섞어서 풀었습니다.

mrcamel   1년 전

DP로 불필요한 부분을 어떻게 줄일 수 있을까요.

D(i, 9) = 1

D(i, 8) = 2

D(i, 7) = 3

D(i, 6) = 4 .. 이렇게 있으면 다 시도 해봐야 하지 않을까요?


답변 달아주셔서 감사합니다.


appa   1년 전

다 시도해보더라도 O(N * M log K)의 시간복잡도를 가지므로 제가 짠 코드는 5036ms에 통과하더라구요.

아래는 제가 대회 당시에 작성했던 코드입니다. 참고하시길 바랍니다.

39번째 줄에 if (d[now.v][now.c] < now.d) continue; 를 넣지 않으니 8초 정도에 AC가 나오고

저 부분을 넣으니 5초 정도에 AC가 나오네요.

문제의 특성상 다익스트라를 돌다보면 D(i, j)가 한 번만 갱신되는 것이 아니라 여러 번 갱신되므로 저 부분이 있고 없고의 차이가 있습니다.

그리고 마지막으로 입력에서 주어지는 간선이 단방향임에 유의하시면 됩니다.

mrcamel   1년 전

다시 답변주셔서 감사합니다.

답변 달아주신 코드보고 참고해서 다시 짜봤는데 잘 안굴러가네요.. 내일 다시 생각해보겠습니다.

즐거운 연말되세요!

amugeona   1년 전

이 문제가 매우 짧게 돌아가던 분들은 비용처리를 그리디로 했더니 됐다는 얘기가 있었던거 같네요. 모든 비용에 대해 DP로 처리하지 않고도...

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