wowoto9772   5달 전

문제를 이런식으로 접근하고 있습니다.


임의의 노드 a, b 사이의 최소 코스트(최소비용 + 최대페널티)를 구할때,


플로이드를 통해서,


a에서 k 까지의 최소 코스트 - 최대페널티x 

에다가  

k에서 b 까지의 최소 코스트 - 최대페널티y

를 더하고

max(최대페널티x, 최대페널티y)를 더하는 방식으로 값을 갱신하고 있습니다.


논리적으로 틀린 해법인가요 ?

Acka   5달 전

d를 (i, j)간의 최소거리, t를 (i, j)에서 최대패널티라고 하면

   i) d[1][2] = 10 & t[1][2] = 5

   ii) d[1][2] = 5 & t[1][2] = 15

가 있을 때 i번을 선택하게 됩니다.


   d[2][3] = 5 & t[2][3] = 20

이 경우 갱신되는 값은

   d[1][3] = 15 & t[1][3] = 20

이 됩니다. 총 코스트 35네요.


하지만 이전 선택지에서 ii번을 선택했다면 갱신되는 값은

   d[1][3] = 10 & t[1][3] = 20

이 되어 총 코스트 30으로 더 효율적인 경우가 발생할 수 있습니다.


wowoto9772   5달 전

치명타 먹었네요. 감사합니다.

wowoto9772   5달 전

하지만 놀라운건, 제 소스코드에서


4 4 1
5 5 20 15
1 4 1
4 2 4
1 2 10
2 3 5

1 3

의 결과가 (30)이 나와요...

Acka   5달 전

진짜 놀랍네요 ...

Acka   5달 전

아마

(1,2) - (2,3)으로 연결한 게 아니라

(1,4) - (4,3)으로 연결이 가능해서 그런 것 같아요.

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