https://www.acmicpc.net/problem/1238
이 문젠데
왜 정답이 되는지 궁금해서
내가 푼 방법은 모든 N에 대해서 다익스트라 알고리즘 써서 풀었거든?
X에 대해 다익스트라 한번 수행하고O(ElogN)
X제외한 N-1에 대해서 다익스트라 수행하고 O(ElogN) * O(N-1)
그럼 총 O(N * ElogN) 시간복잡도가 들어서
N은 1000, M은 1만이라서 ElogN은 최악이면 약 10만정도
10만 * 1000 => 1억정도인데
왜 정답이 됐지? 시간부족할거 같았는데
1억이면 비벼볼만함
왜? 제한시간 1초인데??
1억 = 1초룰이 일반적으로 적용되는 건 맞는데 상대적으로 좀 비싼 연산이 있고, 싼 연산이 있어서 문제마다 달라 단순 더하기, 빼기 같은 연산은 비교적으로 좀 적게 드는 걸로 알고 있어