cocogod   4달 전

우선순위 큐에 정렬은 돈이 적은순으로 정렬합니다.

이제 다익스트라를 이용하여 돈이 총합보다 적고 총시간보다 적고 적은 돈을 

우선순위 큐에 넣으며 확인하였습니다.


반례좀 찾아주세요 ㅠㅠ

qja0950   2달 전

지금 사용한 돈을 기준으로 작은 순서대로 우선순위 큐를 사용하셨는데,


사용한 돈이 적지만 시간이 오래걸리는 경우 vs 사용한 돈이 조금 더 많지만 시간이 적게 걸리는 경우


이 두 경우에서 후자만 문제 조건에 맞는 경로가 될 수 있습니다.


3

100 100

3

1 2 99 99

1 2 100 1

2 3 1 1


이 경우가 반례가 되네요.

100이 나와야하는데 -1이 나옵니다.

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