https://www.acmicpc.net/problem/1848
- 터널 하나가 갈때 올때 서로 값이 다른 것이고 한번만 쓰이는 것임
- 한점만 방문해서는 안되고(1 - 3 - 1 이런것은 안되니까) 2번 이상 방문했을때 최소값을 구하고 싶은데 잘 안되었음(중복해서 점을 방문하는 처리..)
접근1
- 단순하게 k에서 시작해서 k가 아닌 점에서 끝난다고 치고, 1에서 k거리 + k에서 끝나는 점 거리 + 끝나는점에서 1까지 거리를 구하면 됨
- 이를 각 점에 대해서 반복하면.. N M logM 정도 나옴
- 비슷하게 시작점을 들고다니면서 각 점마다 [각점][시작점] 식으로 거리 배열을 가져가는 접근도 해봄
- 대략 5억정도라서 엄청 시간이 많이 걸리거나 타임아웃이 나겠거니 해서 제출해봤는데 메모리 초과가 남
- pq에 엄청 많이 들어가서 나름 가지치기를 해보았지만 실패
접근2
- 모든 시작점에서 시작을 하면서, 1로 방문 하지 않거나(현재 방문한 점이 시작점일 경우, 최초 시작), 시작점에 방문하지 않거나(다음 방문할 점이 시작점일 경우 두번 방문하니까..) 등을 처리했는데 답이 안나옴
- 추측해보면 최소거리를 구하는 과정에서 어떤점 x까지의 최단거리라고 보면 시작점이 a일때 최단거리라서 시작점이 b인 경우는 방문을 못하고.....
- 계속 진행하다보면 시작점이 a인 것들만 살아남는다든지
- 또는 한쪽은 a만 살아남고 한쪽은 b만 살아남아서 결국 연결이 끊긴다든지 이런 예외가 있는 것 같다.
접근3
- 최단거리가 아니고 그 다음 최단거리도 구하면 되지 않을까 어렴풋이 생각은 했지만
- 시작 점에 따라 처리를 어떻게 해야할지 생각이 잘 안서서 고민하던 차에
- 먼저 고민을 하신분께 조언을 얻고 구체화 해서 도전을 해봄
- 최단거리와 그 다음 최단거리를 구해나가기 + 시작점도 같이 저장
- 결과적으로 접근 1에서 2차원 배열의 경우의 수를 줄인 형태인데
- 서로 다른 시작점을 가진 것들로 경로를 구해나가다 보니 각 점에대해서 의미있는 최소 거리를 구한다는 접근인 것 같은데
- 왜 최단거리만으로는 못구하는지, 왜 2개의 거리만으로 반드시 구해지는지(3개를 구하는 것도 아니고 4개를 구하는 것도 아니고) 는 확실히 증명을 못하겠다
newbieski