1. 다익스트라 1번 사용

2. 최단 경로로 갈 수 있는 지점을 저장하여 마지막 부분에서 g,h에 대응되는 경로가 존재하는지 검사

우선 특정 위치(s)에서 모든 곳의 최단 거리를 구하는 다익스트라를 사용했으며

qDist는 s에서의 최단거리를 저장하는 배열이고

qDepart는 최단 거리를 구했을 때 이동해야 하는 가까운 출발지 입니다.

1
2	3	5
	4

인접한 두 노드가 연결되어있다고 할 때

1에서 5로가는 최단 거리는 1-2-3-5 가 되는데

이 때 qDepart[5]에 3을 저장하여

qDepart[3]->qDepart[2]->qDepart[1]로 역 탐색할 수 있게 구현해보았습니다.

마지막에는 위에서 구한 경로로 {g, h}나 {h, g}로 이동한 적 있는 후보가 있을 때

output에 추가해주었고

모든 테스트케이스가 끝나면 output을 순회하며 안에 원소들을 출력하는 식으로 구현되어있습니다.

다른 분들과 비슷하게 30퍼 언저리에서 실패가 뜨네요..

어떤 부분에서 실수를 한걸까요...

g, h가 각각 s와 같다는 테스트케이스도 통과하는 것 처럼 보입니다.

아니면 혹시 g랑 h가 붙어있는것이 아닌 떨어져 있을 수 있나요?

그런 테스트케이스는 없겠죠?

=============================================

여러 게시물을 읽어본 결과 제 코드의 문제점을 발견했습니다.

"비용이 똑같으면 길이 여러 개 일 수 있다" 였습니다.

이 부분을 수정하여 int -> vector<int>로 바꾸어

해당 후보 지점에서 시작 지점으로 최단 거리 이동할 때

모든 경로를 저장하여 {g, h}나 {h, g}가 있는지 검사했습니다.

이전에 33퍼에서 실패가 떴었다면

지금은 66퍼에서 메모리 초과가 뜹니다..

어떤게 또 문제일까요..

처음 50퍼때 메모리 초과 발생하는 것을

전역 변수로 graph, dist등을 이동시켜 66퍼로 연장시켰네요..ㅎ

==============================================

맨 아래 부분에서 최단 경로를 추출하는 중에 {g, h}나 {h, g}를 지나는 간선이 발견된다면

바로 추가해주고 다음 후보자를 검사하도록 하였습니다.

하지만 이건 시간적으로 빨라졌을 뿐 메모리 초과에는 관련이 없는 최적화였네요.. 똑같이 메모리 초기화가 뜹니다.

==============================================

코드 자체를 Dijkstra 3번 사용하는 솔루션으로 바꿔서 제출하여 성공했습니다.