CHILD문제 질문좀 할게요 KimJJ http://algospot.com/judge/problem/read/CHILD 일단 제가 처음 이 문제를 보고나서 한 생각은 먼저 단순한 최단경로 문제를 통해서 1번에서 2번으로 가는 최단경로를 찾은 다음에 여기에 해당하는 간선들의 가중치를 음수로 뒤집어서 다시 벨만-포드 알고리즘을 사용해서 N번으로 가는 최단 거리를 구하는 것이었거든요. 즉 음의 간선이 선택되면 이 간선을 2번으로 갈 때 사용하는 대신 N번으로 갈 때 사용하고, 대신 음의 간선으로 들어가기 전까지 선택되는 간선들을 2번으로 갈 때 사용한다는 생각이었던 거죠 그런데 이게 해보니까 몇 번을 코딩해도 정답이 안 되더라고요. 대체 그래프 구성을 어떻게 해야 하나요? 짜증나서 DFS로 풀어내고 다른 사람들 소스코드를 봤는데 역시 주석 없이는 이해를 못하겠네요 -_-; DFS도 80ms대로 답을 구할 수 있다는게 나름 충격적이기도 하고요.. 11년 전
7개의 댓글이 있습니다. sven 음의 간선 개념이 잘 이해가 안되는데요, 말씀하신 부분을 어떻게 구현하셨나요? 11년 전 link KimJJ sven // 음 실패한 코드를 볼 수 있는 방법이 있으면 쉽게 설명할 수 있을 텐데요. dijkstra 알고리즘으로 2번에서 1번으로 가는 최단경로를 구합니다. 그 다음 통과한 간선들을 '통과한 반대 방향으로' 뒤집고 가중치에 -1을 곱합니다. 이 다음 bellman-ford 알고리즘으로 N번에서 1번으로 가는 최단 거리를 구합니다. 두 최단 거리의 크기를 더하면 1번에서 2번을 거쳐 N번으로 가는 최단 거리와 같아지게 된다.. 뭐 그런 생각이었는데 오답 처리되더라고요 11년 전 link Kureyo 말씀하신대로 하면 될거같은데요 강원님이나 l10veu님 코드가 벨만포드로 길찾고 재귀 함수로 간선을 음수로 뒤집는데 제일 깔끔해보이네요(짧기도 하고) 한 번 참고해보세요 11년 전 link Kureyo (2)-(3)-(1) \ | (4) * cost는 전부 1 제가 리플 제대로 이해했는지 모르겠는데 이 데이타에 대해 한 번 체크해보실래요? 11년 전 link Kureyo 어..깨지네 2-3-4가 삼각형을 이루고 1이 3에 매달려있는거에요 11년 전 link KimJJ N번에서 1번으로 가는 게 아니라 2번으로 가는 경로가 되어야겠네요.. 11년 전 link Being (2)-(3)-(1) \ | (4) * cost는 전부 1 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
KimJJ
http://algospot.com/judge/problem/read/CHILD
일단 제가 처음 이 문제를 보고나서 한 생각은 먼저 단순한 최단경로 문제를 통해서 1번에서 2번으로 가는 최단경로를 찾은 다음에 여기에 해당하는 간선들의 가중치를 음수로 뒤집어서 다시 벨만-포드 알고리즘을 사용해서 N번으로 가는 최단 거리를 구하는 것이었거든요.
즉 음의 간선이 선택되면 이 간선을 2번으로 갈 때 사용하는 대신 N번으로 갈 때 사용하고, 대신 음의 간선으로 들어가기 전까지 선택되는 간선들을 2번으로 갈 때 사용한다는 생각이었던 거죠
그런데 이게 해보니까 몇 번을 코딩해도 정답이 안 되더라고요.
대체 그래프 구성을 어떻게 해야 하나요?
짜증나서 DFS로 풀어내고 다른 사람들 소스코드를 봤는데 역시 주석 없이는 이해를 못하겠네요 -_-; DFS도 80ms대로 답을 구할 수 있다는게 나름 충격적이기도 하고요..
11년 전