18933번 - 최소 스패닝 트리와 쿼리 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 256 MB | 20 | 9 | 7 | 87.500% |
문제
$Path_i$는 $i$ 개의 정점을 가진 방향 그래프로, 모든 $1 \le j < i$ 에 대해 $j \rightarrow j + 1$ 로 가는 간선이 존재한다.
가중치 있는 방향 그래프 $G_1$ 과 방향 그래프 $G_2$ 의 텐서 곱 (tensor product) $G_1 \times G_2$ 는 다음과 같이 정의된다:
- 정점 집합은 $\{(u, v)|u \in G_1, v \in G_2\}$ 의 형태다. 정점 집합의 크기는 $|G_1| \times |G_2|$ 이다.
- 두 정점 $(u_1, v_1), (u_2, v_2)$ 를 잇는 무방향 간선이 존재한다는 것은, $G_1$ 에 $u_1 \rightarrow u_2$ 방향의 간선, $G_2$ 에 $v_1 \rightarrow v_2$ 방향의 간선이 있음을 뜻한다.
- 간선의 가중치는, $G_1$에서 두 정점 $u_1 \rightarrow u_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}$ 에서의 문제의 정답을 출력해야 한다.
예제 입력 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
예제 출력 1
16 23 30 37
예제 입력 2
4 4 8 3 4 12 1 1 20 1 3 22 4 2 12 4 4 2 2 2 2 1 2 2 1 4 2
예제 출력 2
62 80 98 116
예제 입력 3
6 6 15 1 2 1 1 3 1 3 4 1 2 4 1 6 3 2 6 5 2 3 5 2 2 3 2 4 3 2 6 4 2 5 4 2 4 6 2 6 6 2 5 5 3 5 1 3
예제 출력 3
19 28 37 46 55 64
출처
Contest > Open Cup > 2018/2019 Season > Stage 10: Grand Prix of Xi'An A번
- 문제를 번역한 사람: koosaga
© 2022 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호