SSSP (최단 경로 쿼리)

방향 가중치 그래프 $G$와 두 정점 $s$, $t$가 주어졌을 때, $p(s, t)$를 $s$에서 $t$까지 가는 최단 경로의 가중치 합으로 정의한다. $s$에서 $t$로 도달할 수 없으면 $p(s, t)$를 1,000,000,000으로 정의한다.

입력으로는 그래프 $G$와 $Q$개의 쿼리 $(s_1, t_1), (s_2, t_2), \dots, (s_Q, t_Q)$가 주어진다. 각 쿼리 $k$에 대해 $p(s_k, t_k)$를 출력하면 된다.

그래프에는 음의 가중치를 가진 간선이 있을 수 있으나, 가중치 합이 음수인 사이클은 존재하지 않는다.

입력은 두 개의 블록으로 이루어진다. 첫 번째 블록은 그래프 $G$의 인접 리스트를, 두 번째 블록은 쿼리를 나타낸다.

첫 번째 블록의 첫째 줄에는 정점의 개수 $V$가 주어진다. 정점은 $0$번부터 $V-1$번까지 번호가 매겨져 있다. 이어지는 $V$개의 줄에는 $0$번 정점부터 순서대로 각 정점의 정보가 주어진다. 각 줄의 첫 번째 수 $n_i$는 정점 $i$에서 나가는 간선의 개수이며, 그 뒤로 $n_i$개의 쌍 $(j, w)$가 이어진다. 각 쌍은 정점 $i$에서 정점 $j$로 향하는 가중치 $w$인 간선을 뜻한다.

두 번째 블록의 첫째 줄에는 쿼리의 개수 $Q$가 주어지고, 이어지는 $Q$개의 줄에 각각 $s_k$와 $t_k$가 주어진다.

한 줄에서 연속한 두 정수는 공백으로 구분된다. 입력은 다음 조건을 만족한다.

1. $0 < V \le 300$
2. $n_i$는 음이 아닌 정수이다.
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. 그래프 $G$에는 가중치 합이 음수인 사이클이 존재하지 않는다.

$Q$개의 줄을 출력한다. $k$번째 줄에는 $p(s_k, t_k)$의 값을 출력한다.

마지막 줄에는 아래 "힌트"에 정의된 알고리즘을 수행하는 동안 누적된 counter 변수의 최종 값을 다음 형식으로 출력한다.

The value of counter is: <counter>

각 쿼리 $(s_k, t_k)$는 아래의 큐 기반 벨만-포드(SPFA) 알고리즘으로 처리한다. counter 변수는 모든 쿼리에 걸쳐 값이 누적되며, 쿼리마다 초기화하지 않는다.

counter ← 0
입력에 주어진 순서대로 각 쿼리 (s, t)에 대해:
    모든 정점 v에 대해 dist[v] ← ∞,  그리고 dist[s] ← 0
    모든 정점 v에 대해 inQueue[v] ← false
    FIFO 큐를 비우고 s를 넣는다
    inQueue[s] ← true;   counter ← counter + 1
    큐가 빌 때까지 반복:
        u ← 큐에서 하나 꺼낸다;   inQueue[u] ← false
        정점 u의 인접 리스트에 있는 각 간선 (u → v, 가중치 w)를 입력 순서대로:
            만약 dist[u] + w < dist[v] 이면:
                dist[v] ← dist[u] + w
                만약 inQueue[v] = false 이면:
                    큐에 v를 넣는다;   inQueue[v] ← true;   counter ← counter + 1
    p(s, t) = (dist[t] < ∞ 이면 dist[t], 그렇지 않으면 1,000,000,000)

정리하면 counter는 알고리즘 전체에서 정점이 큐에 삽입된 총 횟수이다. 각 쿼리 시작 시 출발점 $s$를 큐에 넣는 것도 1회로 센다.