백준 13911 - 집 구하기 (C++)

문제 문제 링크 BOJ 13911 - 집 구하기 문제 요약 이사 갈 지역의 지도가 그래프로 주어지고 맥도날드 및 스타벅스의 위치 정보가 주어진다. 문제에 정의된 $3$가지 조건을 만족하면서, 맥도날드 및 스타벅스까지의 거리 합이 최소가 되는 집을 찾아보자.

제한 TL : $1$ sec, ML : $256$ MB $3 ≤ V ≤ 10,000$ $1 ≤ w ≤ 10,000$ $0 ≤ E ≤ 300,000$ $1 ≤ x, y ≤ 100,000,000 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 풀이 우선 다익을 이용하는 문제란 것은 쉽게 알아 챌 수 있다. 당연히 모든 집에서 다익을 돌려보는 것은 간선의 개수가 많아 $TLE$ 확정일 듯 싶다.

역으로 맥도날드, 스타벅스의 입장으로부터.....