다익스트라

14284 : 간선 이어가기 2접근처음엔 단순하게 간선과 가중치가 나오길래 최소 신장 트리를 생각했었다. 하지만, 모든 정점을 연결하는 것이 아닌 특정 정점 두 개만 연결시켜야 했고 최소신장트리로는 풀 수 없음을 느꼈다. 그 다음으로 생각한 것은 유니온 파인드인데, 이것도 두 정점을 연결했을 때 최소 비용임을 보장할 수 없다. 마지막으로 생각한 것은 다익스트라였다. 모든 정점을 다 고려해도 두 정점 간의 최소 비용으로 연결을 보장한다.간선 연결 과정에서 최악의 형태는 1자형태로 쭉 뻗은 그래프 형태가 되는데, 그렇게 되면 간선이 N - 1개가 된다. 그렇다면 최대 100,000개의 간선에는 중복이 있을 수 밖에 없다. 따라서, 그래프 저장시 가중치가 더 낮은 간선 취하면 될 듯 싶었다.풀이풀 때는 중복되..