31815번 - Construct a Graph 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 374 | 106 | 86 | 31.273% |
문제
$N\times N$ 크기의 행렬 $D$가 있다. 당신은 정점이 $N$개이고 아래 조건들을 만족하는 무방향 연결 그래프를 구성해야 한다. 각 정점은 $1$부터 $N$까지 번호가 매겨져 있으며, 각 간선에는 양의 정수 가중치를 원하는 대로 부여할 수 있다.
- 모든 정점 쌍 $(u,v)$에 대해, $u$와 $v$ 사이의 최단 경로의 길이는 $D_{u,v}$이다.
- 모든 간선의 가중치의 합은 가능한 최소여야 한다.
조건을 만족하는 그래프가 존재하는지 판별하고, 있다면 그 중 아무거나 하나를 출력하라.
입력
첫 번째 줄에 정점의 개수를 나타내는 정수 $N$이 주어진다.
다음 $N$개 줄 중 $i$번째 줄에는 $N$개의 정수 $D_{i,1},D_{i,2},\ldots ,D_{i,N}$이 공백으로 구분되어 주어진다.
출력
문제의 조건을 만족하는 그래프가 존재하지 않는다면, $-1$을 출력한다.
조건을 만족하는 그래프가 존재한다면,
- 첫 번째 줄에 간선의 개수를 나타내는 정수 $M$을 출력한다.
- 다음 $M$개 줄 중 $i$번째 줄에 세 정수 $u_i$, $v_i$, $c_i$를 공백으로 구분하여 출력한다. 이것은 $i$번 간선이 두 정점 $u_i$와 $v_i$를 잇고 가중치가 $c_i$라는 것을 나타낸다.
- 같은 쌍의 정점을 연결하는 간선은 최대 하나여야 하고, 각 간선의 가중치는 $10^9$ 이하여야 한다.
제한
- $2\leq N\leq 300$
- $D_{i,i}=0$ ($1\le i\le N$)
- $1\leq D_{i,j}=D_{j,i}\leq 10^9$ ($1\le i<j\le N$)
- $1\leq u_i,v_i\leq N$ ($1\le i\le M$)
- $u_i\neq v_i$ ($1\le i\le M$)
- $1\leq c_i\leq 10^9$ ($1\le i\le M$)
- 같은 쌍의 정점을 연결하는 간선은 최대 하나여야 한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | 이 서브태스크에서는 조건을 만족하는 그래프가 존재하는지만 판별해도 된다. 즉, 채점 프로그램은 출력이 $-1$인지 아닌지의 여부만 확인한다. |
| 2 | 19 | $N \leq 50$ |
| 3 | 72 | 추가적인 제약 조건이 없다. |
예제 입력 1
3 0 1 2 1 0 3 2 3 0
예제 출력 1
2 1 2 1 1 3 2
예제 입력 2
3 0 1 3 1 0 1 3 1 0
예제 출력 2
-1
출처
University > KAIST > KAIST RUN Spring Contest > 2024 KAIST RUN Spring Contest C번
- 문제를 만든 사람: flakepowders
- 문제를 검수한 사람: 79brue, abra_stone, ai4youej, flappybird, koosaga, octane, parkky, qwerasdfzxcl
채점 및 기타 정보
- 예제는 채점하지 않는다.