2)start 정점을 1로 하고 완전 탐색 실시 하는데, 방문 하려는 노드까지 오는 cost가 다익스트라를 이용해 구한 결과와 동일한 경우에만 계속 탐색 실시.
최종 목적지에 도달하면, 해당 목적지에 오는데 거쳐간 cnt++ (예를 들어 1에서 출발하여 최종 목적지 8이라 할때, 경로가 1 3 4 8이라 하면 cnt[1]++, cnt[3]++, cnt[4]++, cnt[8]++
3)주인공이 방문 하려는 곳이 2일 경우 cnt[2] 나누기 GDC(cnt[2], cnt[8]) / cnt[8] 나누기 GDC(cnt[2], cnt[8]) 출력
이렇게 알고리즘을 구현했는데....
변경
1)다익스트라를 각 노드를 시작정점으로 하여 각 노드로부터 다른 모든 노드에 이르는 최단 거리 구함.(플로이드 구현)
2)start 정점을 1로 하고 완전 탐색 실시 하는데, 함수 선언은
func(시작 정점, end 정점)로함.
방문 하려는 노드까지 오는 cost가 다익스트라를 이용해 구한 결과와 동일한 경우에만 계속 탐색 실시.
&& 다익스트라(플로이드 버전)의 결과가 distance[start][end]에 저장되어 있다면
distance[1][최종 목적지] == distance[1][임의의 노드] + distance[임의의 노드][최종목적지] 인 경우만 탐색 실시
3)
주인공이 방문 하려는 곳이 2일 경우
result1 = func(1, end 정점)
result2 = func(1, 2) * func(2, end정점)
result2 나누기 GDC(result2, result1) / result1 나누기 GDC(result2, result1) 출력
이렇게 알고리즘을 구현했는데....
여전히...TC 20개도 못돌리더라구요...(타임아웃)
혹시 알고리즘 팁 있으면 조언 부탁드립니다...ㅠㅠ
인터넷에서 해당 문제 관련 정보를 찾으려는데 도저히 못찾겠어서요...ㅠㅠ
chochogogo
안녕하세요?
바쁘신 중에 또또 질문드려 죄송합니다...
다름이 아니오라 기본 알고리즘이 잘못 됬다는 것을 느끼고 변형 시켜 보았는데요...
2)start 정점을 1로 하고 완전 탐색 실시 하는데, 방문 하려는 노드까지 오는 cost가 다익스트라를 이용해 구한 결과와 동일한 경우에만 계속 탐색 실시.
최종 목적지에 도달하면, 해당 목적지에 오는데 거쳐간 cnt++ (예를 들어 1에서 출발하여 최종 목적지 8이라 할때, 경로가 1 3 4 8이라 하면 cnt[1]++, cnt[3]++, cnt[4]++, cnt[8]++
3)주인공이 방문 하려는 곳이 2일 경우 cnt[2] 나누기 GDC(cnt[2], cnt[8]) / cnt[8] 나누기 GDC(cnt[2], cnt[8]) 출력
이렇게 알고리즘을 구현했는데....
2)start 정점을 1로 하고 완전 탐색 실시 하는데, 함수 선언은
func(시작 정점, end 정점)로함.
방문 하려는 노드까지 오는 cost가 다익스트라를 이용해 구한 결과와 동일한 경우에만 계속 탐색 실시.
&& 다익스트라(플로이드 버전)의 결과가 distance[start][end]에 저장되어 있다면
distance[1][최종 목적지] == distance[1][임의의 노드] + distance[임의의 노드][최종목적지] 인 경우만 탐색 실시
3)
주인공이 방문 하려는 곳이 2일 경우
result1 = func(1, end 정점)
result2 = func(1, 2) * func(2, end정점)
result2 나누기 GDC(result2, result1) / result1 나누기 GDC(result2, result1) 출력
이렇게 알고리즘을 구현했는데....
여전히...TC 20개도 못돌리더라구요...(타임아웃)
혹시 알고리즘 팁 있으면 조언 부탁드립니다...ㅠㅠ
인터넷에서 해당 문제 관련 정보를 찾으려는데 도저히 못찾겠어서요...ㅠㅠ
9년 전