boj 1238 : 파티

boj 1238 : 파티

https://www.acmicpc.net/problem/1238

시간초과가 나지 않겠나? 라는 의문을 가졌지만, 잘 생각해본다면 단 두번의 다익스트라로 해결이 가능하다.^^..

우선 파티장소에서 모든마을까지는 단순한 다익스트라의 구현으로 구할 수 있다.

그렇다면 각각의 마을에서 파티장소까지의 경로는 어떻게 구할 수 있을까?

답은 경로를 거꾸로 저장한 edge를 저장하는 것으로 해결 가능하다.

a->z 경로의 최단거리는 반대경로의 최단거리와 같다.

호기심에 floyd로 시간초과인지 테스트해보았지만 역시나 시간초과^^