번 마을부터 각 마을까지의 최단거리 중 가장 긴 것을 찾아야 합니다.
가중치가 이상인 방향 그래프에서의 단일 출발점 최단경로 문제이므로 데이크스트라 알고리즘을 떠올릴 수 있습니다.
다만 고행의 길로 인해 간선이 최대 개 존재하므로, 미리 간선을 만든다면 시간 혹은 메모리가 부족합니다.
그래프의 특성을 이용하거나 자료 구조를 활용하여 시간과 메모리를 개선할 수 있습니다.
를 만족하는 가 존재하면 이를 라 하겠습니다.
한 마을에서 출발하는 고행의 길이 연결하는 마을들의 격은 항상 구간 꼴로 나타납니다.
이때 가 단조증가한다는 성질을 이용할 수 있습니다.
각 에 대응하는 정점 과, 모든 에 대해 간선 와 을 만듭니다.
가 단조증가하므로, 이면서 가장 작은 를 구해 간선 을 만들면 모든 고행의 길을 개의 간선으로 모델링할 수 있습니다.
그대로 데이크스트라 알고리즘을 사용하면 에 문제를 해결할 수 있습니다.
특수한 모델링 없이, 자료구조를 활용한 방법도 소개합니다.
데이크스트라 알고리즘을 진행하면서 각 간선을 한 번에 방문하는 방법을 찾아야 합니다.
데이크스트라에서 정점들까지의 거리를 업데이트할 때, 특정 위치가 아닌 구간을 업데이트할 수 있으면 됩니다.
우선순위 큐의 용도로 느리게 갱신되는 세그먼트 트리를 사용하면 구간 업데이트 연산을 지원할 수 있습니다.
모든 편한 길을 최대 한 번 방문하여 세그먼트 트리를 업데이트하고, 각 정점 방문 시에 구간 업데이트가 한 번 일어나므로 에 문제를 풀 수 있습니다.
단, 이미 최단경로가 확정된 정점이 구간 업데이트의 영향을 받게 된다면 각 정점을 최대 번 방문하게 되어 전체 시간복잡도가 이 됨에 주의해야 합니다.
이를 막기 위해 더 이상 업데이트하지 않음을 나타내는, 무한대를 나타내는 값보다 작은 값을 도입할 수 있습니다.