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으로 더 효율적인 경우가 발생할 수 있습니다.

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

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

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

1 3

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

진짜 놀랍네요 ...

아마

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

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