다익스트라를 초과시키는 그래프

프로그래밍 대회용 테스트 데이터를 만드는 일은 어렵다. 좋은 데이터는 문제의 의도에 맞게 짠 코드와 그렇지 않은 코드를 가려내야 한다. 대부분의 입력에서는 맞지만 특수한 입력에서만 틀리는 코드도 잡아야 한다.

이 문제는 최단 경로 프로그램 두 개를 구분하는 방향 가중치 그래프를 출력한다. 그래프 $X$는 다음을 만족해야 한다.

1. 코드 A(플로이드-워셜)가 $X$를 처리할 때 시간 초과가 나면 안 된다.
2. 코드 B(변형 다익스트라)가 $X$를 처리할 때 시간 초과가 나야 한다.

각 코드는 연산 횟수를 세는 카운터를 둔다. 카운터 값이 $10^6$을 넘으면 시간 초과이다. 데이터는 작을수록 좋으므로 출력하는 정수는 $157$개 이하여야 한다.

플로이드-워셜은 정점 수 $V$에 대해 카운터를 정확히 $V^3$만큼 올린다. 따라서 $V \le 100$이면 코드 A는 시간 초과가 아니다.

변형 다익스트라는 우선순위 큐에 같은 정점을 여러 번 넣는다. 음수 간선이 있으면 큐에서 꺼내는 횟수가 지수로 늘 수 있다. 아래 삼각형 장치를 $k$개 이어 붙이면 변형 다익스트라의 카운터는 지수로 커지고, 플로이드-워셜의 카운터는 $(2k+1)^3$에 머문다.

조건을 만족하는 그래프는 여럿일 수 있다. 채점은 아래 규칙으로 유일하게 정해진 그래프만 정답으로 본다.

$V = 2k+1$로 두고 정점 번호는 $0$부터 $2k$까지로 둔다. 간선은 모두 방향 간선이다.

• 정점 $0$의 나가는 간선은 없다.
• 정점 $1$은 정점 $0$으로 가중치 $1$인 간선 하나를 보낸다.
• 정점 $2$는 정점 $1$로 가중치 $1$인 간선 하나를 보낸다.
• 각 정수 $t = 1, 2, \ldots, k-1$에 대해 다음을 따른다.
  • 정점 $2t+1$은 정점 $2t$로 가중치 $-2 \cdot 2^{t}$인 간선 하나를 보낸다.
  • 정점 $2t+2$는 두 간선을 보낸다. 첫 간선은 정점 $2t+1$로 가고 가중치는 $2^{t}$이다. 둘째 간선은 정점 $2t$로 가고 가중치는 $0$이다.

질의는 하나이다. 시작 정점은 $2k$이고 도착 정점은 $0$이다.

첫 줄에 삼각형 장치의 개수 $k$가 주어진다. ($1 \le k \le 16$)

이 $k$에 대해 $V = 2k+1 \le 33$이므로 플로이드-워셜 카운터는 $10^6$을 넘지 않는다. 출력 정수 개수는 $8k+3$이며 $157$ 이하이다. 모든 가중치 $w$는 $|w| < 10^6$을 만족한다.

위에서 정한 그래프를 다음 형식으로 출력한다.

첫 줄에 정점 수 $V$를 출력한다.

다음 $V$줄 가운데 $i$번째 줄은 정점 $i$의 나가는 간선을 적는다. $i$는 $0$부터 시작한다. 줄의 첫 정수 $n_i$는 나가는 간선의 개수이다. 그 뒤에 $n_i$개의 정수 쌍 $j$ $w$를 한 칸으로 구분해 출력한다. $j$는 도착 정점이고 $w$는 가중치이다. 한 정점에 간선이 여러 개이면 문제에서 적은 순서대로 출력한다.

그다음 줄에 질의 수 $1$을 출력한다.

마지막 줄에 $2k$와 $0$을 한 칸으로 구분해 출력한다.

코드 A와 코드 B의 카운터는 다음 의사 코드처럼 움직인다.

플로이드-워셜:

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

변형 다익스트라 (질의마다 반복):

dist[s] = 0
pq.push((0, s))
while pq is not empty
    counter = counter + 1
    (d, u) = pq.pop()
    if d == dist[u]
        for each edge (u, v, w) from u
            if dist[u] + w < dist[v]
                dist[v] = dist[u] + w
                pq.push((dist[v], v))

우선순위 큐는 거리 값이 더 작은 쌍을 먼저 꺼낸다.