blackbee4   2년 전

문제 설명에 보시면 버스 노선의 가중치는 100001을 넘지 않는 것으로 기술되어있으나, BUS 리스트의 초기화 값, 즉 INF 값을 100001으로 잡았을 때 오답이 나왔습니다. INF값을 훨씬 더 늘려서야 정답을 받을 수 있었습니다. 확인 부탁드립니다.

제출 번호 - 81068760(오답), 81068762(정답)

jtw7913   2년 전

https://www.acmicpc.net/source...

assert문으로 확인한 결과 데이터는 문제가 없습니다. 


zenith82114   2년 전

버스 하나의 비용과 경로 전체의 비용을 혼동하지 않았는지 다시 확인해보세요.

djm03178   2년 전

각 버스의 비용이 최대 100000이므로 최악의 경우 n-1개의 버스를 타면 99900000의 비용이 듭니다.

wizardrabbit   2년 전

안녕하세요 질문자님, 인접 행렬을 이용해서 버스 간의 거리를 저장하는 식으로 그래프를 구성해주셨군요. 그리고, 지나갈 수 없는 길임을 표현하기 위해 초깃값을 할당해 주셨군요.

하지만, 간선의 최대 가중치인 $100\,000$보다 $1$ 큰 $100\,001$을 초깃값으로 하기에는 너무 초깃값이 작을 것입니다. 지나갈 수 없는 길임을 표현하기 위해 초깃값을 표현하려면, 최악의 상황에서 가장 긴 경로로 통행했을 때보다도(길 하나만 거치는 케이스뿐만 아니라 여러 개의 길을 거치는 케이스도요!) 더 가중치가 커야 할 겁니다. 어떤 상황에서든 초깃값으로 설정된 경로를 절대 지나지 않는 것이 답이여야 한다는 것에 유의해 주세요. 아래의 반례를 드리겠습니다.

preview
입력:
3
2
1 2 100000
2 3 100000
1 3

정답:
200000
3
1 2 3

출력:
100001
2
1 3

첫 번째 답변자님이 남겨주신 댓글대로, 데이터에 대한 합리적인 의심을 하실 때는 assert문을 사용해 엄밀하게 검증해 보실 것을 권장드립니다.

blackbee4   2년 전

다들 도움 주셔서 감사합니다.

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