Making test data 3

Programming contests are common. Writing a good contest problem is hard, and making the test data is the hardest part. Good tests separate a program written to the intended algorithm from one that is not. They should also catch a program that is right on most inputs and wrong on a special case.

This task does not ask you to submit a shortest-path solver. It asks you to print one test file in the single-source shortest path (SSSP) format.

Sungkeun must build a file $X$ that separates code A (OptimizedBellmanFord) from code B (FloydWarshall). Both programs keep an iteration count in counter. If counter exceeds $C$, the run is a time limit exceeded (TLE). In the sources in the hint, the literal 1000000 is replaced by $C$ in this problem.

File $X$ must satisfy all of the following.

1. Code A must not TLE on $X$.
2. Code B must TLE on $X$.
3. $X$ consists of at most $T$ integers.

The SSSP input format is as follows.

The first line contains the number of vertices $V$. Vertices are numbered $0$ through $V-1$. Then $V$ lines follow. The line for vertex $i$ ($0 \le i < V$) starts with $n_i$, the number of outgoing edges, then $n_i$ pairs $j$ $w$. $j$ is the head and $w$ is the weight. The next line contains the number of queries $Q$. Each of the next $Q$ lines contains $s_k$ and $t_k$.

The file must also obey these constraints.

• $1 \le V \le 300$
• $n_i$ is a non-negative integer
• $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$
• The graph has no cycle whose weights sum to a negative value

If several files work, choose the lexicographically smallest sequence of integers. Compare from the left. At the first position where they differ, the sequence with the smaller integer comes first. If one sequence is a prefix of the other, the shorter one comes first.

If no such file exists, print -1.

The first line contains two integers $C$ and $T$.

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

If no valid file exists, print -1 on one line.

Otherwise print an SSSP input file. Separate integers on the same line with a single space. Do not put a trailing space at the end of a line.

Print $V$ on the first line. Then print $V$ lines. The line for vertex $i$ (with $i$ starting at $0$) starts with $n_i$, the number of outgoing edges, followed by $n_i$ pairs $j$ $w$. If there are no outgoing edges, print only 0. Then print $Q$. Then print $Q$ lines, each with $s$ and $t$ for one query.

Code A is optimized Bellman-Ford. Code B is Floyd-Warshall. In the sources below, the literal 1000000 is replaced by the input $C$. If counter exceeds $C$, the program stops as TLE.

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;
}

Floyd-Warshall increments counter exactly $V^3$ times, regardless of the number of edges or queries. Optimized Bellman-Ford stops a query early when a round makes no update.