데이터 만들기 3

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

이 문제는 최단 경로를 구하는 프로그램을 제출하는 문제가 아니다. 단일 출발 최단 경로(SSSP) 형식의 테스트 데이터 하나를 출력하는 문제이다.

상근이는 코드 A(OptimizedBellmanFord)와 코드 B(FloydWarshall)를 구별하는 데이터 $X$를 만들어야 한다. 두 코드는 내부 반복 횟수를 counter에 담는다. counter가 $C$를 넘으면 시간 초과이다. 힌트 소스의 리터럴 1000000은 이 문제에서 $C$로 바꾼다.

데이터 $X$는 다음을 모두 만족해야 한다.

1. 코드 A가 $X$를 처리할 때 시간 초과가 나면 안 된다.
2. 코드 B가 $X$를 처리할 때 시간 초과가 나야 한다.
3. $X$를 이루는 정수는 $T$개 이하이다.

SSSP 입력 형식은 다음과 같다.

첫째 줄에 정점 수 $V$가 나온다. 정점 번호는 $0$부터 $V-1$까지이다. 다음 $V$개 줄 중 $i$번째 줄($0 \le i < V$)에는 정점 $i$에서 나가는 간선 수 $n_i$가 나오고, 이어서 $n_i$개의 쌍 $j$ $w$가 나온다. $j$는 도착 정점이고 $w$는 가중치이다. 그다음 줄에 쿼리 수 $Q$가 나온다. 다음 $Q$개 줄에 $s_k$와 $t_k$가 나온다.

데이터는 아래 조건을 모두 지켜야 한다.

• $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_k, t_k < V$
• 가중치 합이 음수인 사이클이 없다

조건을 만족하는 데이터가 여러 개이면, 정수 수열로 보았을 때 사전 순으로 가장 작은 것을 고른다. 앞에서부터 비교해 처음으로 다른 위치에서 더 작은 정수를 가진 수열이 앞선다. 한쪽이 다른 쪽의 접두사이면 짧은 쪽이 앞선다.

그런 데이터가 없으면 -1을 출력한다.

첫째 줄에 정수 $C$와 $T$가 주어진다.

• $0 \le C \le 10^9$
• $1 \le T \le 10^5$

조건을 만족하는 데이터가 없으면 한 줄에 -1을 출력한다.

있으면 SSSP 입력 형식 그대로 출력한다. 같은 줄의 정수는 공백 하나로 구분하고, 줄 끝에 공백을 두지 않는다.

첫째 줄에 $V$를 출력한다. 다음 $V$줄 가운데 $i$번째 줄($i$는 $0$부터)에는 정점 $i$의 나가는 간선 개수 $n_i$를 쓰고, 이어서 $n_i$개의 쌍 $j$ $w$를 쓴다. 나가는 간선이 없으면 0만 쓴다. 그다음 줄에 $Q$를 출력한다. 다음 $Q$줄에 각 쿼리의 $s$와 $t$를 공백으로 구분해 출력한다.

코드 A는 최적화 벨만-포드이고, 코드 B는 플로이드-워셜이다. 아래 소스에서 리터럴 1000000은 입력 $C$로 바꾼다. counter가 $C$를 넘으면 시간 초과로 종료한다.

OptimizedBellmanFord:

#define INF 1000000000

int i, j, u, vv, w_u_vv, V, n, w, Q, counter, s, t;
int dist[1000];
int AdjList[1000][1000];
int weight[1000][1000];
int sz[1000];
int change;

int main() {
  scanf("%d", &V);
  for (i = 0; i < V; i++) {
    scanf("%d", &n);
    sz[i] = 0;
    while (n--) {
      scanf("%d %d", &j, &w);
      AdjList[i][sz[i]] = j;
      weight[i][sz[i]] = w;
      sz[i]++;
    }
  }
  counter = 0;
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &s, &t);
    for (i = 0; i < V; i++) dist[i] = INF;
    dist[s] = 0;
    for (i = 0; i < V-1; i++) {
      change = 0;
      for (u = 0; u < V; u++)
        for (j = 0; j < sz[u]; j++) {
          counter++;
          if (counter > 1000000) {
            printf("TLE because iteration counter > 1000000\n");
            return 1;
          }
          vv = AdjList[u][j];
          w_u_vv = weight[u][j];
          if (dist[u] + w_u_vv < dist[vv]) {
            dist[vv] = dist[u] + w_u_vv;
            change = 1;
          }
        }
      if (!change)
        break;
    }
    printf("%d\n", dist[t]);
  }
  printf("The value of counter is: %d\n", counter);
  return 0;
}

FloydWarshall:

int i, j, k, V, n, w, M[300][300], counter, Q, s, t;

int main() {
  scanf("%d", &V);
  for (i = 0; i < V; i++)
    for (j = i+1; j < V; j++)
      M[i][j] = M[j][i] = 1000000000;
  for (i = 0; i < V; i++)
    M[i][i] = 0;
  for (i = 0; i < V; i++) {
    scanf("%d", &n);
    while (n--) {
      scanf("%d %d", &j, &w);
      if (w < M[i][j]) M[i][j] = w;
    }
  }
  counter = 0;
  for (k = 0; k < V; k++)
    for (i = 0; i < V; i++)
      for (j = 0; j < V; j++) {
        counter++;
        if (counter > 1000000) {
          printf("TLE because iteration counter > 1000000\n");
          return 1;
        }
        if (M[i][k] + M[k][j] < M[i][j]) M[i][j] = M[i][k] + M[k][j];
      }
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &s, &t);
    printf("%d\n", M[s][t]);
  }
  printf("The value of counter is: %d\n", counter);
  return 0;
}

플로이드-워셜은 간선 수와 쿼리와 관계없이 $V^3$번 counter를 올린다. 최적화 벨만-포드는 한 라운드에서 갱신이 없으면 그 쿼리를 일찍 끝낸다.