gydnjs2009   1년 전

2 3
1 2 1
2 1 100
1 1 100

답 100

2 3
1 1 100
1 2 1
2 1 100

답 100

잘못된 답 101

다익스트라로 풀던 중 조건처리를 잘못해서 통과가 안되던 문제가 있었는데

해당 문제 반례 하나 놓고갑니다 다익스트라로 푸시는 분들 참고해보세요

junsong96   1년 전

입력

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.

라고 되어있는데요, 

(2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 에서 

E ≤ V(V-1) 라는 의미는

자기 자신으로 가는 간선이 존재하지 않는다고 생각하는게 맞지 않나요?

자기 자신으로 가는 간선이 존재할 때 E ≤ V2 꼴이 되어야 성립한다고 생각하는데

반례로 들어주신 두 가지 모두 1 1 100 이 포함되어 있어서 댓글 남겨봅니다

hagentexx   11달 전

다익스트라가 아닌 플로이드-워셜로 풀어서 정답을 맞춘 뉴비인데용

정답 맞춘 코드로 해당 예시를 입력하면 둘 다 100이 아닌 101으로 값으로 나옵니다.

자기 자신에게 가는 간선이 존재하는게 맞으나, 데이터에 없어서 통과되는건지 아님 애초에  자기 자신에게 가는 간선이 없는게 맞는 건지 정확히 모르겠으나

저도 자기 자신에게 가는 간선이 없다고 생각하고 풀었기에, 윗분이 적어주신 것처럼 자기 자신에게 가는 간선이 없다고 생각하고 푸는 게 맞다고 생각해요!

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