Graph that exceeds Dijkstra's counter

Writing contest test data is hard. Good data must separate a solution that matches the problem from one that does not. It must also catch a program that is right on most inputs and wrong on a special case.

This problem asks you to print a directed weighted graph that separates two shortest-path programs. Graph $X$ must satisfy both of the following.

1. Program A (Floyd-Warshall) must not time out on $X$.
2. Program B (modified Dijkstra) must time out on $X$.

Each program keeps a counter of operations. If the counter exceeds $10^6$, the run is a time out. Smaller data is better, so the printed graph may contain at most $157$ integers.

Floyd-Warshall raises its counter by exactly $V^3$ for a graph with $V$ vertices. If $V \le 100$, program A does not time out.

Modified Dijkstra may push the same vertex onto a priority queue more than once. Negative edges can make the number of pops grow exponentially. Chaining $k$ triangle gadgets below makes the modified Dijkstra counter grow exponentially, while the Floyd-Warshall counter stays $(2k+1)^3$.

Many graphs meet the time-out conditions. The judge accepts only the unique graph defined by the rules below.

Set $V = 2k+1$ and number vertices from $0$ to $2k$. Every edge is directed.

• Vertex $0$ has no outgoing edges.
• Vertex $1$ has one edge to vertex $0$ with weight $1$.
• Vertex $2$ has one edge to vertex $1$ with weight $1$.
• For each integer $t = 1, 2, \ldots, k-1$ do the following.
  • Vertex $2t+1$ has one edge to vertex $2t$ with weight $-2 \cdot 2^{t}$.
  • Vertex $2t+2$ has two edges. The first goes to vertex $2t+1$ with weight $2^{t}$. The second goes to vertex $2t$ with weight $0$.

There is one query. The source is $2k$ and the target is $0$.

The first line contains the number of triangle gadgets $k$. ($1 \le k \le 16$)

For this $k$, $V = 2k+1 \le 33$, so the Floyd-Warshall counter does not exceed $10^6$. The number of printed integers is $8k+3$, which is at most $157$. Every weight $w$ satisfies $|w| < 10^6$.

Print the graph defined above in the following format.

Print $V$ on the first line.

The next $V$ lines describe outgoing edges. Line $i$ (with $i$ starting at $0$) starts with $n_i$, the number of outgoing edges of vertex $i$, then $n_i$ pairs $j$ $w$ separated by spaces. $j$ is the head and $w$ is the weight. If a vertex has more than one edge, print them in the order given in the statement.

Print $1$ on the next line, the number of queries.

Print $2k$ and $0$ on the last line, separated by a space.

The counters in programs A and B follow the pseudocode below.

Floyd-Warshall:

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

Modified Dijkstra (once per query):

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

The priority queue pops the pair with the smaller distance first.