out degree

[python3] 백준 1238 풀이 ( 파티, 다익스트라 )

이번 문제는 참신했다. 물론 내가 생각도 못해서 참신하게 느껴진거 겠지만ㅋㅋ 우선 문제를 보자 문제를 읽어보면 여러 곳에서 학생들이 X마을로 모인다. 이후에 각자 집으로 돌아갈 때 가장 오래 걸리는 학생의 소요 시간을 출력한다. 간단히 생각해보면 파티에 참석하는 경우 마을이 N개 이기 때문에 N -> X로 가는 경우의 수가 나올것이다. 파티가 끝나고 집에 가는 경우는 X -> N으로 가는 경우의 수가 나온다. 그럼 단순하게 보면 단일 시작점 알고리즘이 적용되면 안 되는거 같다. 왜냐하면 출발할 때 N개의 마을에서 각자 출발하기 때문이다. 그래서 나도 플로이드-워샬을 적용하고 풀고자 했다. N=1000 이므로 N^3 = 1,000,000,000 = 10억, 21억 넘지 않아서 괜찮을 줄 알았다. (찾아보니..