최단 경로 테스트 데이터 만들기

프로그래밍 대회용 그래프 문제를 내려면, 의도한 해법은 통과하고 느린 해법은 시간 초과가 나도록 테스트 데이터를 만들어야 한다. 이 문제는 그런 데이터를 출력한다. 조건을 만족하는 데이터가 여러 개일 수 있으므로, 아래에서 정한 구성만 출력한다.

대상은 가중치 있는 유향 그래프의 최단 경로이다. 정점 번호는 $0$부터 $V-1$까지이다. 질의 $(s, t)$에 대해 $s$에서 $t$로 가는 최단 경로의 가중치 합을 $p(s, t)$라 한다. 도달할 수 없으면 $p(s, t) = 10^9$이다.

두 구현의 시간 초과는 코드 안의 counter가 $10^6$을 넘는 것으로 판정한다.

플로이드-워셜은 인접 행렬에서 아래를 수행하므로 counter는 항상 $V^3$이다. $V \le 100$이면 시간 초과가 아니다.

counter = 0
for k = 0 to V-1:
    for i = 0 to V-1:
        for j = 0 to V-1:
            counter += 1
            M[i][j] = min(M[i][j], M[i][k] + M[k][j])

최적화된 벨만-포드는 각 질의마다 거리를 초기화한 다음, 인접 리스트의 모든 간선을 최대 $V-1$라운드 완화한다. 정점은 $0$번부터 $V-1$번 순서로 본다. 한 라운드에서 갱신이 없으면 즉시 중단한다. counter는 간선을 볼 때마다 $1$ 증가한다.

counter = 0
for each query (s, t):
    set dist[v] = 10^9 for every vertex v
    dist[s] = 0
    repeat V-1 times:
        change = false
        for each edge (u, v) in adjacency-list order:
            counter += 1
            if dist[u] + weight(u, v) < dist[v]:
                dist[v] = dist[u] + weight(u, v)
                change = true
        if change is false:
            break

출력할 그래프는 다음으로 유일하게 정한다.

정점 $V$개를 $0, 1, \ldots, V-1$로 둔다. 각 $i = 1, 2, \ldots, V-1$에 대해 정점 $i$에서 정점 $i-1$로 가는 가중치 $1$인 간선을 하나 둔다. 정점 $0$에는 가중치 $1$인 자기 루프를 $K$개 둔다. $K$는 다음을 모두 만족하는 가장 큰 음이 아닌 정수이다.

• 간선 수 $E = (V-1)+K$가 $5000$ 이하이다.
• 출력에 들어가는 정수의 개수 $F = 3V + 2Q + 2K$가 $T$ 이하이다.

질의는 $Q$개이고, 모두 시작점이 $V-1$, 끝점이 $0$이다.

이 구성에서 플로이드-워셜의 counter는 $V^3$이다. 최적화된 벨만-포드는 매 라운드 체인을 한 칸만 완화하므로 $V-1$라운드를 모두 수행하고, counter는 $Q \times E \times (V-1)$이다. $V = 100$, $Q = 10$, $T = 2222$이면 플로이드-워셜은 시간 초과가 아니고 최적화된 벨만-포드는 시간 초과이다.

첫째 줄에 정점 수 $V$, 질의 수 $Q$, 정수 개수 상한 $T$가 공백으로 구분되어 주어진다.

$2 \le V \le 100$

$1 \le Q \le 10$

$3V + 2Q \le T \le 2222$

최단 경로 문제의 입력 형식 그대로 출력한다.

첫째 줄에 $V$를 출력한다.

다음 $V$줄에는 정점 $0$부터 $V-1$까지 나가는 간선을 출력한다. 각 줄의 첫 수는 나가는 간선 수 $n_i$이고, 그 뒤에 $n_i$개의 정수 쌍 $j$ $w$가 온다. $j$는 도착 정점, $w$는 가중치이다.

• 정점 $0$: $n_0 = K$이고, $K$개의 쌍은 모두 $0$ $1$이다.
• 정점 $i$ ($1 \le i \le V-1$): $n_i = 1$이고, 쌍은 $i-1$ $1$이다.

그 다음 줄에 $Q$를 출력한다.

다음 $Q$줄에 각 질의의 시작점과 끝점을 출력한다. 모든 줄은 $V-1$ $0$이다.

한 줄에서 인접한 두 정수 사이에는 공백 하나를 둔다. 줄 끝에 공백을 두지 않는다.

출력에 들어가는 정수는 다음과 같이 센다. $V$ 한 개, 각 정점의 $n_i$를 합한 $V$개, 각 간선의 $(j, w)$를 합한 $2E$개, $Q$ 한 개, 각 질의의 $(s, t)$를 합한 $2Q$개이다. 따라서 $F = V + 2E + 2Q + 2$이고, $E = (V-1)+K$를 대입하면 $F = 3V + 2Q + 2K$이다.

그래프는 다음도 만족해야 한다. 간선 가중치의 절댓값은 $10^6$ 미만이고, 질의의 시작점에서 도달 가능한 음수 사이클은 없다. 위 구성은 가중치가 모두 $1$이므로 이 조건을 지킨다.

자기 루프의 가중치가 양수이면, 정점 $0$을 자기 루프로 갱신하는 일은 일어나지 않는다. 체인 $V-1 \to V-2 \to \cdots \to 0$만 매 라운드 한 칸씩 완화된다.