baek1134   10달 전

500정도로 알고있었는데 n이 1000인데도 플로이드와샬이된다고 되어있어서요!

플로이드와샬이 n^3인데 n 1000까지는 플로이드와샬이 돌아가는건가요?

yukariko   10달 전

간단한 가지치기로 시간안에 해결되는 경우가 많아서 넣은것 같습니다.

highalps   10달 전

조금 더 생각해보면 2nlog(n) 으로 풀리는 문제입니다

algospot   10달 전

구태여 이문제에 힙다익스트라 쓸필요까진 없어보이고

그냥 다익스트라 2번쓰는 것이 사고확장에 도움이 될거같습니다.

포인트는 2번쓴다는 것에 있는 것 같습니다~

zmfldlwl   8달 전

다익스트라를 단 두번만 써서 정답을 도출해낼 수가 있나요...??

저는 입력 에제에서


1,2 + 2,1 구해서 최대값 갱ㅇ신

2,3 + 3,2 구해서 갱신

2,4 + 4,2 구해서 갱신


총 3번 했는ㄷ...

highalps   8달 전

zmfldlwl


예를 들어 1->2 로 가는 길이가 3이라고 해봅시다.

그렇다면 방향을 반대로 바꾼다면 1<-2 가 되겠죠. 이렇게 하면 2에서 1로가는 거리를 구하면 1에서 2로 가는 거리처럼 동일하게 구할 수 있습니다.


결론적으로 X번 마을에서 다익스트라를 돌려서 각 마을까지의 최단거리를 구하고,

그래프의 방향을 모두 바꿔서 다시 X번 마을에서 다익스트라를 돌리면 이때는 1번마을에서 X번마을까지의 거리,......, N번마을에서 X번마을 까지의 거리를 구할 수 있죠

zmfldlwl   8달 전

같은 원리로 소스 수정해서 풀었는데... 시간초과가 나서요.

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