25953번 - 템포럴 그래프 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 607 | 183 | 149 | 31.838% |
문제
템포럴 그래프는 시간의 흐름에 따라 변화하는 관계를 표현하는 자료 구조이다. 템포럴 그래프를 구성하는 정점 집합 $V$는 시간의 흐름에 따라 변하지 않으며, 정점의 개수가 $n ≥ 1$이라 할 때 $V$는 $\{0, 1, \dots , n - 1\}$으로 나타낸다. 시간 표기 $T$는 양의 정수 $1, 2, \dots , t$의 값을 가지며 시간 표기가 차례로 증가하는 것으로 시간의 흐름을 표현한다. 각 시간 표기 $T$에서 양의 정수인 가중치를 가지는 간선들의 집합 $E_T$가 정의되고, $E_T$에 포함되는 간선의 수는 일정하게 유지된다. 아래 그림은 정점 집합 $V = \{0, 1, 2, 3, 4\}$와 시간 표기 $T = 1, 2, 3, 4$에서 정의된 템포럴 그래프의 예시이다.
템포럴 그래프의 한 정점에서 다른 정점으로 향하는 경로는 증가하는 시간 표기에 따라 차례로 나타나는 간선들의 집합으로 구성된다. 경로를 구성할 때에는 각 시간 표기에서 최대 한 개의 간선을 선택할 수 있으며, 경로를 구성하는 간선들이 정의되는 시간 표기가 연속할 필요는 없다. 예를 들어, 위 그림의 템포럴 그래프에서 세 간선 $(0, 1)$, $(1, 2)$, $(2, 4)$를 각각 시간 표기 $T = 1, 2, 4$에서 선택한다면 이는 정점 $0$에서 정점 $4$로 향하는 경로가 된다. 하지만 세 간선 $(0, 2)$, $(2, 3)$, $(3, 4)$를 각각 시간 표기 $T = 1, 3, 2$에서 선택한다면 이는 정점 $0$에서 정점 $4$로 향하는 경로가 될 수 없다(왜냐하면, 선택된 시간 표기가 증가하지 않기 때문이다). 경로의 길이는 경로에 포함되는 간선의 가중치의 총 합으로 정의한다. 따라서, 두 간선 $(0, 2)$, $(2, 4)$를 각각 시간 표기 $T = 1, 4$에서 선택한다면 이는 정점 $0$에서 정점 $4$로 향하는 최단 길이 경로가 되고 경로의 길이는 $1 + 2 = 3$이 된다.
입력으로 템포럴 그래프와 경로의 시작과 끝이 되는 두 정점 $s$와 $e$가 주어질 때, $s$에서 $e$로 향하는 최단 길이 경로의 길이를 구하는 프로그램을 작성하시오.
입력
입력은 표준입력을 사용한다. 첫 번째 줄에 정점 집합의 크기를 나타내는 양의 정수 $n$ ($2 ≤ n ≤ 10\,000$), 시간 표기의 범위를 나타내는 양의 정수 $t$ ($1 ≤ t ≤ 1\,000$), 매 시간 표기마다 정의되는 간선들의 개수를 나타내는 양의 정수 $m$ ($1 ≤ m ≤ 1\,000$)이 차례로 주어진다. 다음 줄에 경로의 시작이 되는 정점을 나타내는 정수 $s$와 경로의 끝이 되는 정점을 나타내는 정수 $e$ ($0 ≤ s ≠ e ≤ n - 1$)가 차례로 주어진다. 이어지는 $m$개의 줄은 시간 표기 $T = 1$에서 정의되는 간선들의 정보를 나타낸다. 특정한 두 정점을 연결하는 간선이 두 개 이상 나타나는 경우는 없다. 각 줄에는 간선이 연결하는 두 정점의 번호와 간선의 가중치를 나타내는 양의 정수 $w$ ($1 ≤ w ≤ 10\,000$)가 차례로 주어진다. 이어지는 $m × (t − 1)$줄은 시간 표기 $T = 2, \dots , t$에서 정의되는 간선들의 정보를 동일한 방식으로 나타낸다.
출력
출력은 표준출력을 사용한다. 정점 $s$에서 정점 $e$로 향하는 최단 길이 경로의 길이를 한 줄에 출력하고, 경로가 정의되지 않는 경우에는 $-1$을 출력한다.
예제 입력 1
5 4 3 0 4 0 1 1 0 2 1 2 4 3 0 3 3 1 2 3 3 4 2 0 4 5 1 4 4 2 3 4 0 1 2 1 2 3 2 4 2
예제 출력 1
3
예제 입력 2
5 4 2 0 4 0 1 1 0 2 1 1 2 3 3 4 2 1 2 3 2 3 4 0 1 2 1 2 3
예제 출력 2
-1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호