시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 16 | 6 | 6 | 85.714% |
$Path_i$는 $i$ 개의 정점을 가진 방향 그래프로, 모든 $1 \le j < i$ 에 대해 $j \rightarrow j + 1$ 로 가는 간선이 존재한다.
가중치 있는 방향 그래프 $G_1$ 과 방향 그래프 $G_2$ 의 텐서 곱 (tensor product) $G_1 \times G_2$ 는 다음과 같이 정의된다:
$N$ 개의 정점과 $M$ 개의 간선을 가진 방향 그래프 $G$ 가 입력으로 주어진다. 각 간선에는 양의 정수 가중치가 부여되어 있다. $G \times Path_i$ 라는 그래프를 생각하자. 이 그래프는 무방향이고 각 간선에 양의 정수 가중치가 부여되어 있다. 모든 $2 \le i \le Q + 1$에 대해, $G \times Path_i$ 의 최소 스패닝 트리의 간선 가중치 합을 출력하라. 쿼리로 들어오는 모든 $G \times Path_i$ 에 대해 스패닝 트리가 항상 존재하게끔 입력이 주어짐이 보장된다.
첫 번째 줄에 세 정수 $N, Q, M$ 이 주어진다. ($1 \le N, Q \le 100\,000, 1 \le M \le 200\,000$)
이후 $M$ 개의 줄에 세 개의 정수 $u_i, v_i, w_i$ 가 주어진다. $u_i \rightarrow v_i$ 방향의 가중치 $w_i$ 의 간선이 존재한다는 뜻이다. ($1 \le u_i, v_i \le N, 1 \le w_i \le 30$)
$Q$ 개의 줄을 출력하라. 이 중 $i$ 번째 줄에는 $G \times Path_{i + 1}$ 에서의 문제의 정답을 출력해야 한다.
4 4 8 3 4 1 1 1 3 1 3 2 4 2 4 4 4 2 2 2 3 1 2 2 1 4 3
16 23 30 37