Making shortest-path test data

A graph problem for a programming contest needs test data that lets an intended solution finish and makes a slow solution exceed the time limit. This task asks you to print such data. Many graphs can meet the time-limit conditions, so print only the construction fixed below.

The target problem is shortest paths on a directed weighted graph. Vertices are numbered $0$ to $V-1$. For a query $(s, t)$, let $p(s, t)$ be the total weight of a shortest path from $s$ to $t$. If $t$ is unreachable from $s$, then $p(s, t) = 10^9$.

Both implementations treat a run as time limit exceeded when counter in the code exceeds $10^6$.

Floyd-Warshall runs the nested loops below on an adjacency matrix, so counter is always $V^3$. If $V \le 100$, Floyd-Warshall does not exceed the time limit.

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

Optimized Bellman-Ford, for each query, resets distances and then relaxes every adjacency-list edge for at most $V-1$ rounds. Vertices are scanned from $0$ to $V-1$. If a round makes no update, the loop stops. counter increases by $1$ each time an edge is examined.

counter = 0
for each query (s, t):
    set dist[v] = 10^9 for every vertex v
    dist[s] = 0
    repeat V-1 times:
        change = false
        for each edge (u, v) in adjacency-list order:
            counter += 1
            if dist[u] + weight(u, v) < dist[v]:
                dist[v] = dist[u] + weight(u, v)
                change = true
        if change is false:
            break

The graph you print is uniquely determined as follows.

There are $V$ vertices $0, 1, \ldots, V-1$. For each $i = 1, 2, \ldots, V-1$, put one edge from $i$ to $i-1$ with weight $1$. Vertex $0$ has $K$ self-loops of weight $1$. $K$ is the largest nonnegative integer that satisfies both of the following.

• The number of edges $E = (V-1)+K$ is at most $5000$.
• The number of integers in the output $F = 3V + 2Q + 2K$ is at most $T$.

There are $Q$ queries, each with source $V-1$ and target $0$.

On this graph, Floyd-Warshall's counter is $V^3$. Optimized Bellman-Ford relaxes one hop of the chain per round, so it runs all $V-1$ rounds and counter equals $Q \times E \times (V-1)$. When $V = 100$, $Q = 10$, and $T = 2222$, Floyd-Warshall does not exceed the time limit and optimized Bellman-Ford does.

The first line contains three integers $V$, $Q$, and $T$: the number of vertices, the number of queries, and the upper bound on the number of integers in the output.

$2 \le V \le 100$

$1 \le Q \le 10$

$3V + 2Q \le T \le 2222$

Print the data in the shortest-path input format.

Print $V$ on the first line.

Then print $V$ lines for vertices $0$ through $V-1$. Each line starts with the out-degree $n_i$, followed by $n_i$ pairs $j$ $w$, where $j$ is the head and $w$ is the weight.

• Vertex $0$: $n_0 = K$, and every pair is $0$ $1$.
• Vertex $i$ ($1 \le i \le V-1$): $n_i = 1$, and the pair is $i-1$ $1$.

Print $Q$ on the next line.

Then print $Q$ query lines. Every line is $V-1$ $0$.

Separate adjacent integers on a line with a single space. Do not put trailing spaces.

Count integers in the output as follows. One integer for $V$, $V$ integers for the out-degrees $n_i$, $2E$ integers for the pairs $(j, w)$, one integer for $Q$, and $2Q$ integers for the pairs $(s, t)$. Hence $F = V + 2E + 2Q + 2$. Substituting $E = (V-1)+K$ gives $F = 3V + 2Q + 2K$.

The graph must also satisfy the following. Every edge weight has absolute value less than $10^6$, and no negative cycle is reachable from a query source. All weights in this construction are $1$, so both hold.

A positive self-loop never improves the distance of vertex $0$. Only the chain $V-1 \to V-2 \to \cdots \to 0$ is relaxed, one hop per round.