Making test data 5

Writing a contest problem is hard, and the hardest part is often the test data. Good tests separate a solution that matches the intended algorithm from one that does not.

This task does not ask you to compute shortest paths. It asks you to print a directed weighted graph that separates two implementations.

Code A is ModifiedDijkstra. Code B is OptimizedBellmanFord. Both keep a counter. If the counter exceeds $10^6$, the run is treated as time limit exceeded.

Graph $X$ must satisfy the following.

1. Code A must not exceed the time limit on $X$.
2. Code B must exceed the time limit on $X$.

Many graphs would work, so the graph is fixed by the following rules.

Vertices are numbered $0$ through $V-1$.

• Vertex $0$ has $S$ self-loops of weight $1$. If $S = 0$, it has no outgoing edges.
• For each $i = 1, 2, \ldots, V-1$, vertex $i$ has exactly one outgoing edge to vertex $i-1$ of weight $1$.
• There are $Q$ queries, each from $V-1$ to $0$.

The graph is a chain with nonnegative weights. ModifiedDijkstra pops each vertex from the priority queue about once. OptimizedBellmanFord scans vertices in order $0, 1, \ldots, V-1$, so one full sweep advances the distance along the chain by a single hop. Self-loops at vertex $0$ raise the edge count and do not create a shorter path.

The first line contains three integers $V$, $S$, and $Q$.

• $1 \le V \le 300$
• $0 \le S$
• $1 \le Q \le 10$
• The number of edges $V - 1 + S$ is at most $5000$.

Print the graph and the queries in the format below. 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$, where $j$ is the head and $w$ is the weight.

Then print $Q$.

Then print $Q$ lines, each with the source and the target of one query.

Pseudocode for the two implementations follows. The counter is the time-limit meter.

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]

Edges are scanned from smaller vertex indices to larger ones. Edges of the same vertex are scanned in the order they are printed.