먼저 목표 지점인 포르투에서부터 각 정점까지의 최단 거리 rd를 너비 우선 탐색으로 구해야 한다. 이 거리를 기준으로 하면 모든 최단 경로는 거리 값이 1씩 줄어드는 방향으로만 내려간다. 경찰이 지연 효과를 내기 위해서는 이러한 최단 경로 상의 도로를 끊어야 하므로, 거리 차가 0 또는 1인 두 정점 사이의 도로들만이 차단 후보가 된다.
BFS 과정에서 최단 거리 트리를 만들고, 트리 간선이 아닌 후보 도로마다 (rd[u]+rd[v], u, v)라는 3중 튜플을 모은다. 첫 번째 성분인 rd[u]+rd[v]는 u, v에서 각각 부모로 가는 도로가 끊겼을 때 서포터즈가 다른 쪽으로 우회하기 시작하는 시간을 의미한다. 이를 오름차순으로 정렬한 뒤, 거리 트리 위에서 유니온 파인드를 이용해 두 정점을 가장 가까운 공통 조상까지 서서히 끌어올리면서 지나가는 모든 정점 x에 대해 srd[x] = min(srd[x], rd[v] + 1)을 갱신한다. srd[x]는 x에서 트리 상의 부모로 가는 길이 막혔을 때 다른 경로를 통해서 도달하는 최단경로이다. 트리 상에서 두 경로가 만날 때까지 이러한 병합을 반복하면 모든 정점의 srd가 채워진다.
이제부터는실제 이동 횟수를 최소화하는 경로를 찾으면 된다. 이를 위해 다익스트라와 동일한 구조의 우선순위 큐 탐색을 수행하되, 간선 가중치를 1로 두는 대신 도착 후보 시각 t = max(ans[cur] + 1, srd[nxt])를 사용한다. 즉, 현 위치까지 걸린 이동 횟수에 1을 더한 값과 srd 중 더 큰 쪽이 해당 정점에 도착하는 최단 시각이 된다. 큐 안에서 가장 작은 t를 가진 항목부터 꺼내며 갱신을 진행하면 결국 리스본에 대한 ans[1]이 경찰의 방해를 감안한 최소 이동 횟수가 된다.
