1162번 도로포장
백준 1162번 도로포장 풀이. 도로를 몇 번 포장했는지 상태에 포함한 다익스트라로 K개 이하 도로를 무료화한 최단 거리를 구한다.
모든 태그
주제
#dijkstra
8편의 기록
-
-
백준 10217번 KCM Travel
백준 10217번 KCM Travel 풀이. 사용한 비용을 상태로 두고 각 비용에서 가능한 최소 시간을 관리하는 최단 경로 접근을 정리한다.
-
백준 2211번 네트워크 복구
백준 2211번 네트워크 복구 풀이. 1번 노드 기준 다익스트라를 수행하며 각 노드의 부모 간선을 저장해 복구할 네트워크를 만든다.
-
백준 5719번 거의 최단 경로
백준 5719번 거의 최단 경로 풀이. 모든 최단 경로에 포함된 간선을 역추적으로 제거한 뒤 다시 다익스트라를 수행한다.
-
백준 10473번 인간 대포
백준 10473번 인간 대포 풀이. 시작점, 대포, 목적지를 완전 그래프로 만들고 걷기와 대포 이동 시간을 비교해 다익스트라를 적용한다.
-
백준 15422번 Bumped!
백준 15422번 Bumped! 풀이. 비행기 티켓 사용 전후를 두 그래프 층으로 나누고 0비용 간선을 연결해 최단 시간을 구한다.
-
백준 1504번 특정한 최단 경로
백준 1504번 특정한 최단 경로 풀이. 다익스트라를 여러 번 실행해 v1, v2를 지나는 두 경로 후보 중 더 짧은 값을 선택한다.
-
백준 1753번 최단경로
백준 1753번 최단경로 풀이. 우선순위 큐를 사용한 다익스트라로 시작 정점에서 모든 정점까지의 최단 거리를 구한다.