[BOJ] 최소 비용 구하기

[kimdevspace]

문제 링크 https://www.acmicpc.net/problem/1916

풀이 사항 풀이 일자: 2024.00.00 풀이 시간: 00분 00초 채점 결과: 오답/시간 초과/런타임 에러/정답 예상 문제 유형: 구현/BFS/DFS/DP/자료구조/문자열 등 시간: 00 ms 메모리: 00 kb

풀이 방법 (풀이 접근 및 방법에 대한 설명 문제를 풀지 못했다면 어느 곳에서 어려움을 느꼈는지 적어주세요!!)

[kimdevspace]

문제링크

259

풀이 사항

• 풀이 일자 : 240920
• 풀이 시간 : 20분
• 채점 결과 : 정답
• 예상 문제 유형 : 최단 경로
• 시간 : 476ms
• 메모리 : 50,720kb

  풀이 방법

• 테케에 있는 비용들이 모두 양수이므로 다익스트라 알고리즘 사용해서 최단 경로 구하기 다익스트라
  1. 거리 배열 만들어서 스타트노드는 0으로, 나머지는 MaxValue로 초기
  2. 그리디 알고리즘이므로 우선순위 큐에 cost가 작은 순으로 간선들을 담기
  3. 탐색 중 연결된 노드들이 이전 노드들간의 거리보다 작은 값일 경우 pq에 넣기
  4. 엔드노드의 거리 출력!