1865번 - 웜홀
정점이 반드시 모두 연결되어야 한다는 조건이 빠져있습니다. 서로 연결되어 있지 않은 서로 다른 그래프 두 개가 입력될 경우 시작 지점을 따로 지정해서 해결해야 한다고 생각합니다. 정점은 반드시 모두 연결되어 있다. 라는 조건을 추가해야하지 않을까요?
연결되어 있지 않으면 어떤 문제가 발생하나요? 정답이 항상 NO가 되는 것뿐일 것 같습니다.
1에 연결되어 있는 그래프는 NO이지만 1과 연결되어 있지 않은 다른 그래프에서는 다시 자신으로 음수의 길이로 돌아올 수 있다는 거죠. 그러면 YES로 출력해야하지 않나요?
그런 경우라면 답이 YES가 되는 것이고, 그것이 어떤 문제를 야기하는지 모르겠습니다.
22035361 이 분의 코드를 보면 무조건 1로 돌아와야만 YES로 받아들이고 있는데도 정답처리가 되었습니다. 1로 돌아오지 않고 YES를 만족하는 케이스가 없는게 아닐까요? 아니면, 제가 이 분의 코드를 잘못 이해한건가요..?
감사합니다, 드디어 이해가 됬습니다. 1에서 출발해도 모든 점에서 최단경로를 계산하면 음의 회로를 돌면 결국 N번째 이후로도 갱신이 될 거니까요. 그런데 위 코드는 무조건 edge[j][1]==1을 만족해야만 true를 반환하는데 이는 어떻게 가능한건가요?
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
lemonoyaa 4년 전
정점이 반드시 모두 연결되어야 한다는 조건이 빠져있습니다. 서로 연결되어 있지 않은 서로 다른 그래프 두 개가 입력될 경우 시작 지점을 따로 지정해서 해결해야 한다고 생각합니다. 정점은 반드시 모두 연결되어 있다. 라는 조건을 추가해야하지 않을까요?