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

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

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

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

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

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

저는 입력 에제에서

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

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

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

총 3번 했는ㄷ...

zmfldlwl

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

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

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

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

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