데이터 만들기 5

프로그래밍 대회용 문제를 낼 때 가장 어려운 일 중 하나는 테스트 데이터를 만드는 일이다. 좋은 테스트 데이터는 문제의 의도에 맞게 짠 코드와 그렇지 않은 코드를 구별해야 한다.

이 문제는 최단 경로를 구하는 프로그램을 제출하는 문제가 아니다. 두 구현을 구분하는 방향 가중치 그래프를 출력하는 문제이다.

코드 A는 수정 다익스트라(ModifiedDijkstra)이고, 코드 B는 최적화 벨만-포드(OptimizedBellmanFord)이다. 두 코드는 모두 카운터를 유지하며, 카운터가 $10^6$을 넘으면 시간 초과이다.

출력할 그래프 $X$는 다음을 만족해야 한다.

1. 코드 A가 $X$를 처리할 때 시간 초과가 나면 안 된다.
2. 코드 B가 $X$를 처리할 때 시간 초과가 나야 한다.

아무 그래프나 허용하면 정답이 여러 개이므로, 그래프는 아래 규칙으로 유일하게 정한다.

정점은 $0$부터 $V-1$까지이다.

• 정점 $0$은 가중치 $1$인 자기 루프를 $S$개 가진다. $S = 0$이면 나가는 변이 없다.
• 각 $i = 1, 2, \ldots, V-1$에 대해 정점 $i$는 정점 $i-1$로 가는 가중치 $1$인 변을 정확히 하나 가진다.
• 질의는 $Q$개이고, 모두 시작점이 $V-1$, 도착점이 $0$이다.

이 그래프는 음이 아닌 가중치의 체인이다. 수정 다익스트라는 각 정점을 우선순위 큐에서 거의 한 번씩만 꺼낸다. 최적화 벨만-포드는 정점을 $0, 1, \ldots, V-1$ 순서로 스캔하므로, 한 번의 전체 스윕에서 최단 거리 정보가 체인을 따라 한 칸만 전파된다. 정점 $0$의 자기 루프는 변의 개수만 늘리고 더 짧은 경로는 만들지 않는다.

첫째 줄에 정수 $V$, $S$, $Q$가 주어진다.

• $1 \le V \le 300$
• $0 \le S$
• $1 \le Q \le 10$
• 변의 총개수 $V - 1 + S$는 $5000$ 이하이다.

그래프와 질의를 아래 형식으로 출력한다. 같은 줄의 정수는 공백 하나로 구분하고, 줄 끝에는 공백을 두지 않는다.

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

다음 $V$줄 가운데 $i$번째 줄($i$는 $0$부터)에는 정점 $i$의 나가는 변 개수 $n_i$를 쓰고, 이어서 $n_i$개의 쌍 $j$ $w$를 쓴다. $j$는 도착 정점이고 $w$는 가중치이다.

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

다음 $Q$줄에 각 질의의 시작점과 도착점을 공백으로 구분해 출력한다.

수정 다익스트라와 최적화 벨만-포드의 의사코드는 다음과 같다. 카운터는 시간 한도를 재는 값이다.

ModifiedDijkstra
counter = 0
for each query (s, t):
    dist[u] = INF for all u
    dist[s] = 0
    pq.push((0, s))
    while pq is not empty:
        counter += 1
        (d, u) = pq.pop()
        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))
    output dist[t]

OptimizedBellmanFord
counter = 0
for each query (s, t):
    dist[u] = INF for all u
    dist[s] = 0
    loop V - 1 times:
        change = false
        for each edge (u, v, w) in adjacency list order:
            counter += 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                change = true
        if change is false:
            break
    output dist[t]

변은 정점 번호가 작은 것부터, 같은 정점에서는 출력에 적은 순서대로 스캔한다.