문제 개요

N개의 마을이 있고, 각 마을은 재건 완료 시간 t[i]를 가집니다. 마을 간 도로는 양방향이며 가중치 w를 갖습니다. Q개의 쿼리 (u, v, T)가 주어질 때, 시간 T까지 재건된 마을만 통행 가능할 때 u에서 v까지의 최단 거리를 구해야 합니다. 데이터는 T가 비내림차순으로 주어집니다.

잘못된 접근: 다익스트라 + 시간 기반 그래프 추가

처음 생각한 방법은 쿼리를 시간순 정렬 후, 각 시간대별로 재건 완료된 마을의 간선을 그래프에 추가하며 다익스트라를 실행하는 것입니다. 하지만 이는 O(Q * M * log N)으로 8e9 수준의 연산이 필요해 O2 최적화 없이는 통과하기 어렵습니다. 또한, "데이터는 t가 비내림차순" 조건을 간과해 일부 케이스에서 오답이 발생할 수 있습니다.

// 의사코드: 잘못된 접근 예시
sort(queries by T)
for each query (u, v, T):
    if u == v: answer = 0
    else if t[u] > T or t[v] > T: answer = -1
    else:
        while next_time <= T:
            add_edges_for_rebuilt_village()
        run_dijkstra(u)
        answer = dis[v] or -1

올바른 접근: Floyd-Warshall 변형

핵심 아이디어는 Floyd-Warshall 알고리즘의 원리를 역이용하는 것입니다. 도로는 처음부터 모두 개방하되, 중간 경유지(k)로 사용할 수 있는 마을을 재건 완료 시간에 따라 점진적으로 허용하는 것입니다. 즉, k번 마을이 재건 완료되면, 해당 마을을 경유하는 모든 쌍의 최단 거리를 갱신합니다. 이렇게 하면 각 쿼리마다 O(N^2) 갱신만으로 최단 거리를 유지할 수 있습니다.

// 핵심 코드 (C++ 스타일)
int now = 0;
t[0] = -1;
t[N+1] = INF;
for each query (u, v, T):
    while (t[now + 1] <= T):
        now++;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                road[i][j] = min(road[i][j], road[i][now] + road[now][j]);
    if (t[u] > t[now] || t[v] > t[now] || road[u][v] == INF)
        print -1;
    else
        print road[u][v];

왜 이 방법이 동작하는가?

Floyd 알고리즘에서 중간 경유점 k를 1부터 N까지 순차적으로 추가하면, k까지의 경유점만 사용한 최단 경로가 보장됩니다. 여기서 k는 마을 번호가 아닌 재건 완료 시간 순서입니다. 시간 T까지 재건된 마을만 경유 가능하므로, 재건 완료 순서대로 k를 하나씩 추가하며 road[][]를 갱신하면 됩니다. 초기 road[][]는 도로가 있는 경우 직접 연결 가중치, 없는 경우 INF로 설정하고, road[i][i]는 0으로 유지합니다.

쿼리 처리 시, 현재 재건된 마을의 최대 시간 t[now]와 u, v의 재건 시간을 비교해 통행 불가능을 판별합니다. 도로 자체는 처음부터 모두 존재하지만, 경유 마을만 제한되므로 이 방식이 올바릅니다.

시간 복잡도

• 초기화: O(N^2 + M)
• 재건 마을 추가: 각 마을당 O(N^2), 총 O(N^3)
• 쿼리당 O(1) (갱신은 마을 추가 시에만 발생)

N ≤ 200, M ≤ 20000이므로 충분히 빠릅니다.