cho.sh

SSSP (최단 경로 쿼리)

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

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

입력으로는 그래프 GG와 QQ개의 쿼리 (s1,t1),(s2,t2),…,(sQ,tQ)(s_1, t_1), (s_2, t_2), \dots, (s_Q, t_Q)가 주어진다. 각 쿼리 kk에 대해 p(sk,tk)p(s_k, t_k)를 출력하면 된다.

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

입력

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

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

두 번째 블록의 첫째 줄에는 쿼리의 개수 QQ가 주어지고, 이어지는 QQ개의 줄에 각각 sks_k와 tkt_k가 주어진다.

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

  1. 0<V≤3000 < V \le 300
  2. nin_i는 음이 아닌 정수이다.
  3. 0≤j<V0 \le j < V
  4. ∣w∣<106|w| < 10^6
  5. 0≤∑i=0V−1ni≤50000 \le \sum_{i=0}^{V-1} n_i \le 5000
  6. 0<Q≤100 < Q \le 10
  7. 0≤sk<V0 \le s_k < V, 0≤tk<V0 \le t_k < V
  8. 그래프 GG에는 가중치 합이 음수인 사이클이 존재하지 않는다.

출력

QQ개의 줄을 출력한다. kk번째 줄에는 p(sk,tk)p(s_k, t_k)의 값을 출력한다.

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

The value of counter is: <counter>

힌트

각 쿼리 (sk,tk)(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는 알고리즘 전체에서 정점이 큐에 삽입된 총 횟수이다. 각 쿼리 시작 시 출발점 ss를 큐에 넣는 것도 1회로 센다.