입력
첫째 줄에 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 이 포함되어 있어서 댓글 남겨봅니다
gydnjs2009 1년 전 6
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
다익스트라로 풀던 중 조건처리를 잘못해서 통과가 안되던 문제가 있었는데
해당 문제 반례 하나 놓고갑니다 다익스트라로 푸시는 분들 참고해보세요