Floyd 알고리즘을 활용한 점진적 도로 재건 문제 해결
문제 개요
N개의 마을이 있고, 각 마을은 재건 완료 시간 t[i]를 가집니다. 마을 간 도로는 양방향이며 가중치 w를 갖습니다.
Q개의 쿼리 (u, v, T)가 주어질 때, 시간 T까지 재건된 마을만 통행 가능할 때 u에서 v까지의 최단 거리를 구해야 합니다.
데이터는 T가 비내림차순으로 주어집니다.
잘못된 접근: 다익스트라 + 시간 기반 그래프 추가
처음 생각한 방법은 ...
6월 22일 16:52에 게시됨