SSSP (Shortest Path Queries)

Given a directed weighted graph $G$ and two vertices $s$ and $t$, let $p(s, t)$ be the sum of the edge weights along a shortest path from $s$ to $t$. If $t$ is unreachable from $s$, define $p(s, t)$ to be 1,000,000,000.

The input consists of the graph $G$ and $Q$ queries $(s_1, t_1), (s_2, t_2), \dots, (s_Q, t_Q)$. For each query $k$, output $p(s_k, t_k)$.

The graph may contain edges with negative weights, but it never contains a cycle whose total weight is negative.

The input is made of two blocks. The first block describes the adjacency list of the graph $G$; the second block describes the queries.

The first line of the first block contains the number of vertices $V$. Vertices are numbered from $0$ to $V-1$. Each of the next $V$ lines describes one vertex, starting from vertex $0$ in order. On each line, the first number $n_i$ is the number of edges leaving vertex $i$, followed by $n_i$ pairs $(j, w)$. Each pair denotes an edge from vertex $i$ to vertex $j$ with weight $w$.

The first line of the second block contains the number of queries $Q$, followed by $Q$ lines, each containing $s_k$ and $t_k$.

Two consecutive integers on the same line are separated by a single space. The input satisfies the following conditions.

1. $0 < V \le 300$
2. $n_i$ is a non-negative integer.
3. $0 \le j < V$
4. $|w| < 10^6$
5. $0 \le \sum_{i=0}^{V-1} n_i \le 5000$
6. $0 < Q \le 10$
7. $0 \le s_k < V$, $0 \le t_k < V$
8. The graph $G$ contains no cycle whose total weight is negative.

Print $Q$ lines. The $k$-th line contains the value of $p(s_k, t_k)$.

On the last line, print the final value of the counter variable accumulated while running the algorithm defined in the "Hint" section below, using the following format.

The value of counter is: <counter>

Each query $(s_k, t_k)$ is processed with the queue-based Bellman-Ford (SPFA) algorithm below. The counter variable accumulates across all queries and is never reset between queries.

counter ← 0
for each query (s, t) in input order:
    dist[v] ← ∞ for every vertex v,  and dist[s] ← 0
    inQueue[v] ← false for every vertex v
    empty the FIFO queue, then push s
    inQueue[s] ← true;   counter ← counter + 1
    while the queue is not empty:
        u ← pop from the queue;   inQueue[u] ← false
        for each edge (u → v, weight w) in u's adjacency list, in input order:
            if dist[u] + w < dist[v]:
                dist[v] ← dist[u] + w
                if inQueue[v] = false:
                    push v;   inQueue[v] ← true;   counter ← counter + 1
    p(s, t) = dist[t] if dist[t] < ∞ else 1,000,000,000

In other words, counter is the total number of times any vertex is pushed onto the queue over the whole run, counting the initial push of the source $s$ at the start of each query as one.