algoshipda   1년 전

그냥 단순하게 다익스트라로 푸는거라고 생각했는데 자꾸 오답 떠서요

a->b로 갈수있으면 b->a로도 갈 수 있는건가 싶어서 넣어봤는데도 안됩니다.


appa   1년 전

답이 long long일 수 있기 때문에 가중치에 해당하는 pair 부분을 long long으로 고쳐주어야하구요.

pair를 정렬할 때, first 먼저 비교하고, second를 보기 때문에 가중치를 first에 위치해야 하는 게 아닌가 싶습니다.

그리고 23번째 줄에 k가 아니라 n입니다.

위의 3가지 사항을 고쳐보았는데도 계속 WA라 저도 잘 모르겠네요.

appa   1년 전

아래는 제가 옛날에 맞았던 소스인데 참고하시길 바라요.

kesakiyo   1년 전

scanf("%d%d%d",&x,&y,&z);

w[x][y]=min(w[x][y], z);

이렇게 고치니까 정답이 뜨네요.

즉 한 도시에서 다른 도시로 갈 수 있는 간선이 여러개가 존재한단 뜻이죠....

그래프 구현할 때 한 도시에서 다른 도시로 갈 수 있는 길이 한 개 또는 없다고 보장이 되어 있지 않으면

인접행렬보다는 인접리스트로 구현을 하는게 훨씬 안전한 방법 같네요.

algoshipda   1년 전

악 두분 다 감사합니다. 드디어 AC 받았습니다.

appa   1년 전

흐앙... kesakiyo님 짱짱..

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