데이터 만들기 1

프로그래밍 대회에 쓸 좋은 문제를 만드는 일은 어렵다. 그중에서도 테스트 데이터를 만드는 일이 가장 어렵다. 좋은 테스트 데이터는 문제의 의도에 맞게 짠 코드와 그렇지 않은 코드를 구별해야 한다. 대부분의 입력에서는 올바른 결과를 내지만 특별한 입력에서만 실패하는 코드도 찾아내야 한다.

이 문제는 최단 경로를 구하는 프로그램을 제출하는 문제가 아니다. 테스트 데이터를 출력하는 문제이다.

여러분은 가중 방향 그래프의 최단 경로 문제용 입력 데이터 $X$를 하나 만들어야 한다. $X$는 아래 두 코드에 대해 다음 조건을 만족해야 한다.

1. 수정 다익스트라가 $X$를 처리할 때 시간 초과가 발생하면 안 된다.
2. 플로이드-워셜이 $X$를 처리할 때 시간 초과가 발생해야 한다.

데이터는 작을수록 좋다. $X$에 등장하는 정수는 최대 $10^7$개이다.

두 코드는 연산 횟수를 세는 변수 $\mathrm{counter}$를 둔다. $\mathrm{counter}$ 값이 $10^6$을 넘으면 시간 초과이다.

$X$는 다음 형식을 따른다.

첫째 줄에 정점 수 $V$가 있다. 정점 번호는 $0$부터 $V-1$까지이다.

다음 $V$개 줄 중 $i$번째 줄은 정점 $i-1$에서 나가는 간선을 나타낸다. 첫 수는 출차수 $n_i$이고, 이어서 $n_i$개의 쌍 $(j, w)$가 온다. 각 쌍은 정점 $i-1$에서 정점 $j$로 가는 가중치 $w$의 간선이다.

그다음 줄에 질의 수 $Q$가 있다. 다음 $Q$개 줄의 각 줄에는 질의의 시작점 $s$와 도착점 $t$가 있다.

데이터는 다음 제한을 지켜야 한다.

• $1 \le V \le 300$
• $n_i$는 $0$ 이상인 정수이다
• $0 \le j < V$
• $|w| < 10^6$
• $0 \le \sum n_i \le 5000$
• $1 \le Q \le 10$
• $0 \le s, t < V$
• 어떤 질의의 시작점도 음수 사이클에 도달하지 않는다

도달할 수 없는 쌍의 최단 거리는 $10^9$으로 둔다.

조건을 만족하는 데이터가 여러 개이면 정수 개수가 가장 적은 것을 고른다. 그것도 여러 개이면 출력에 등장하는 정수를 왼쪽부터 이은 수열을 사전순으로 비교해 가장 앞서는 것을 고른다.

이 문제는 입력이 없다.

위에서 고른 유일한 데이터를 다음처럼 출력한다.

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

다음 $V$개 줄에 각 정점의 출차수와 간선 목록을 출력한다. 간선이 없으면 그 줄에는 $0$만 출력한다.

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

다음 $Q$개 줄에 $s$와 $t$를 공백으로 구분해 출력한다.

플로이드-워셜은 인접 행렬 $M$에서 다음을 수행한다.

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

반복 횟수는 항상 $V^3$이다. 간선 수와 질의 수에 의존하지 않는다.

수정 다익스트라는 각 질의 $(s, t)$마다 다음을 수행한다. 처음에는 $\mathrm{dist}[s] = 0$이고 나머지 정점의 거리는 무한대이다.

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

우선순위 큐에서 꺼낸 횟수가 $\mathrm{counter}$이다. 같은 정점이 여러 번 갱신되면 큐에 여러 번 들어갈 수 있다.