2982번 - 국왕의 방문 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1045 | 432 | 327 | 46.648% |
문제
지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안에 다른 차량이 들어올 수 없게 통제할 것이다. 하지만, 그가 진입하기 전부터 길에 있던 차량은 계속 있을 수 있다.
상근이는 오토바이 소년 승환이의 뒤를 이어 근처에서 피자를 트럭으로 배달하는 사람이다. 상근이는 교통 통제 때문에 배달을 정시에 하지 못해서 짤릴뻔했다.
이미 고둘라 창지즈 영사우드는 상그니 아라비아로 돌아갔다. 하지만 상근이는 고둘라가 한국에 왔었을 때, 어떤 길로 이동을 했어야 배달을 빠르게 할 수 있었는지 알아보려고 한다. 상근이는 고둘라가 이동한 경로를 알고 있다.
도시는 여러 개의 교차로와 교차로를 서로 연결하는 양방향 도로로 모델링할 수 있다. 상근이는 각 도로를 이동하는데 걸리는 시간을 알고 있다. 고둘라가 그 도로를 이동하는데 걸리는 시간도 같다.
예를 들어, 고둘라가 10분이 되던 때에 어떤 도로에 도착했고, 그 도로를 통과하는데 걸리는 시간이 5라고 하자. 그럼 이 도로는 10, 11, 12, 13, 14분에는 진입할 수 없다. 상근이는 9분 이전, 15분 이후에 이 도로에 진입할 수 있다.
상근이가 배달을 하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 상근이는 고둘라가 출발하고 K분이 지난 후에 배달을 시작한다.
입력
첫째 줄에 교차로의 수 N과 도로의 수 M이 주어진다. 교차로는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 1000, 2 ≤ M ≤ 10,000)
둘째 줄에는 네 정수 A, B, K, G가 주어진다. (1 ≤ A, B ≤ N, 0 ≤ K ≤ 1000, 0 ≤ G ≤ 1000) A는 상근이가 배달을 시작하는 교차로, B는 상근이가 배달을 마치는 교차로이다. K는 고둘라가 출발한 시간과 상근이가 출발한 시간의 차이, G는 고둘라가 방문하는 교차로의 개수이다.
셋째 줄에는 G개의 정수가 주어진다.이 정수는 고둘라가 방문하는 교차로이다. 인접한 교차로 사이의 거리를 고둘라가 이동하는 것이다. 항상 도로는 존재하며, 각 도로를 최대 한 번만 이동한다.
넷째 줄부터 M개 줄에는 도로의 정보를 나타내는 세 정수 U, V, L이 주어진다. 교차로 U와 V를 연결하는 도로를 이동하는데 L분이 걸린다는 뜻이다. L은 1보다 크거나 같고, 1000보다 작거나 같은 정수이다.
출력
첫째 줄에 상근이가 배달을 마치는데 필요한 가장 빠른 시간을 출력한다.
예제 입력 1
6 5 1 6 20 4 5 3 2 4 1 2 2 2 3 8 2 4 3 3 6 10 3 5 15
예제 출력 1
21
예제 입력 2
8 9 1 5 5 5 1 2 3 4 5 1 2 8 2 7 4 2 3 10 6 7 40 3 6 5 6 8 3 4 8 4 4 5 5 3 4 23
예제 출력 2
40
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호