celestial   2달 전

시간초과가 나는 것 같은데 일단 제가 짠 코드 자체도 맞는지 궁금하네요ㅜㅜ

도와주시면 감사합니다ㅜㅜ!!

gkgg123   2달 전

제가 C++을 배워본적이 없어서 제대로 분석을 했는지 모르지만 일단 시간초과가 난 이유는 모든 경우에 대해서 다익스트라를 구했기 때문입니다.

이 문제는 총 3번의 다익스트라를 통해서 정답을 구할 수 있습니다.

힌트를 드리자면 양방향이기 때문에 A->B와 B->A의 경로의 값이 같습니다.

그렇기 때문에 A에 대한 다익스트라를 전부 구했다면, 굳이 B의 다익스트라를 다시 구하지 않더라도

A와 B 사이의 경로를 구할 수 있습니다.

이 점을 유의해서 풀어보시면 될것 같습니다.

그리고 제가 C++은 잘 몰라서 왜 그러는지 모르지만 ans를 int로 하면 틀렸습니다가 뜨고 long long을 해야 정답이 나오더군요.

이 두부분만 고치시면 될것 같습니다.

celestial   2달 전

@gkgg123 오오 님 정말 정말 감사합니다!! 한번 다시 고민해보고 도전해보겠습니다. 조언 정말 감사드려요*^^*

댓글을 작성하려면 로그인해야 합니다.