https://www.acmicpc.net/source...
assert문으로 확인한 결과 데이터는 문제가 없습니다.
11779번 - 최소비용 구하기 2
안녕하세요 질문자님, 인접 행렬을 이용해서 버스 간의 거리를 저장하는 식으로 그래프를 구성해주셨군요. 그리고, 지나갈 수 없는 길임을 표현하기 위해 초깃값을 할당해 주셨군요.
하지만, 간선의 최대 가중치인 $100\,000$보다 $1$ 큰 $100\,001$을 초깃값으로 하기에는 너무 초깃값이 작을 것입니다. 지나갈 수 없는 길임을 표현하기 위해 초깃값을 표현하려면, 최악의 상황에서 가장 긴 경로로 통행했을 때보다도(길 하나만 거치는 케이스뿐만 아니라 여러 개의 길을 거치는 케이스도요!) 더 가중치가 커야 할 겁니다. 어떤 상황에서든 초깃값으로 설정된 경로를 절대 지나지 않는 것이 답이여야 한다는 것에 유의해 주세요. 아래의 반례를 드리겠습니다.
입력: 3 2 1 2 100000 2 3 100000 1 3 정답: 200000 3 1 2 3 출력: 100001 2 1 3
첫 번째 답변자님이 남겨주신 댓글대로, 데이터에 대한 합리적인 의심을 하실 때는 assert문을 사용해 엄밀하게 검증해 보실 것을 권장드립니다.
댓글을 작성하려면 로그인해야 합니다.
blackbee4 2년 전
문제 설명에 보시면 버스 노선의 가중치는 100001을 넘지 않는 것으로 기술되어있으나, BUS 리스트의 초기화 값, 즉 INF 값을 100001으로 잡았을 때 오답이 나왔습니다. INF값을 훨씬 더 늘려서야 정답을 받을 수 있었습니다. 확인 부탁드립니다.
제출 번호 - 81068760(오답), 81068762(정답)