[Programmers] Lv3. 합승 택시 요금 | C++
🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑🏻💻 풀이 과정 [1차 시도] 다익스트라 알고리즘 (실패) 출발지(s)로부터 각 노드에 대한 최단 경로 배열을 구해놓고, 각 노드(i)마다 다익스트라 알고리즘을 돌려서 s👉🏻i + i👉🏻a + i👉🏻b 값들 중 최솟값을 구하는 방식으로 풀었습니다. 노드의 개수(N)가 최대 200개라 될 줄 알았는데 효율성 테스트에서 시간 초과가 나더군요. [2차 시도] 플로이드 워셜 알고리즘 (성공) 매 노드마다 다익스트라 알고리즘을 돌린 것이 원인이라 생각되어, 모든 노드 간의 최단 경로를 구할 수 있는..
