주제

#dijkstra

글 8개

백준 1162번 도로포장

2022년 1월 22일 #cpp #dijkstra #ps

포장한 도로 수를 상태로 둔 다익스트라, 방문 여부 대신 거리 비교로 오래된 항목을 거르는 것이 핵심
백준 10217번 KCM Travel

2022년 1월 22일 #cpp #dijkstra #ps

도로포장처럼 사용한 비용을 상태로 두고 비용별 최소 소요 시간을 기록하는 최단 경로
백준 2211번 네트워크 복구

2022년 1월 18일 #cpp #dijkstra #ps

MST처럼 보이지만 1번 기준 다익스트라에서 각 노드의 부모 간선만 남기면 되는 문제
백준 5719번 거의 최단 경로

2022년 1월 18일 #graph #cpp #dijkstra #ps

다익스트라 후 도착점부터 역추적해 모든 최단 경로 간선을 지우고 다시 다익스트라 돌리기
백준 10473번 인간 대포

2022년 1월 16일 #cpp #dijkstra #geometry #ps

시작점, 대포, 목적지를 완전 그래프로 만들고 걷기와 대포 중 빠른 쪽으로 간선을 둔 다익스트라
백준 15422번 Bumped!

2022년 1월 16일 #cpp #dijkstra #ps

티켓을 쓰기 전과 후로 그래프를 두 겹 만들고 비용 0인 간선으로 이은 다익스트라
백준 1504번 특정한 최단 경로

2021년 9월 19일 #dijkstra #ps #python

1→v1→v2→N과 1→v2→v1→N 중 짧은 쪽을 다익스트라 여러 번으로 비교하기
백준 1753번 최단경로

2021년 9월 19일 #dijkstra #ps #python

비용 기준 우선순위 큐 다익스트라, 일반 큐와 노드 번호 기준 정렬로 시간 초과가 났던 실수