5개의 댓글이 있습니다.
-
-
Fate -
D를 노드의 비용으로 정의했고, C[S][E]를 "S에서 시작해 E에 도착하기 위한 최소 비용"으로 정의했습니다. 그런데 문제 특성상 C를 다음과 같이 조건을 걸었습니다.
- C[S][E] 경로 내에 노드 T가 존재한다면, D[T] <= D[E]를 만족한다.
존재하지 않는 경우에는 _MAX값이 들어가고, 정의에 의해 C 배열은 다음과 같은 점화식으로 구해졌습니다.
C[S][E] = min( C[S][E], C[S][T] + C[T][E] )
그리고 이 때 정답은 다음과 같이 구해집니다.
A[S][E] = min( A[S][E], C[S][T] + C[E][T] + D[T] )
그런데 제가 우려하고 있는 부분은 C[S][T]와 C[T][E]가 제대로 구해져있느냐? 하는 부분입니다. 알고리즘과 소스를 보고 잘못된 부분이 있으면 언제든 답변부탁드립니다.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Fate
안녕하세요. 종종 알고스팟에 문제를 푸는 평범한 학생입니다.
최근 DRUNKEN 문제를 풀어서 제출하는데 WA만 잔뜩 맞고 있습니다.
코드를 보면서 검증을 계속하고, 다른 그래프를 그려서 발생할 수 있는 상황들도 만들어보았는데 기대했던 값들이 전부 나오고 있습니다.
그래서 채점에 사용되는 데이터를 받아 어떤 부분을 놓치고 있는지를 보고 싶습니다.
제가 작성한 코드도 공유차 올려봅니다..
만약 데이터를 보내주실 수 있다면 메일 주소도 적어둡니다.
gg7308@naver.com
하루빨리 AC받고 싶네요. TT
9년 전