8012번 - 한동이는 영업사원! 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1686 | 950 | 760 | 55.841% |
문제
한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 따라, 한동이는 회사에서 돌아야 할 도시의 목록을 받고, 그 목록대로 도시를 여행한다. 회사에서 주는 여행지 목록은 정말 안타깝게도 최적화되어 있지가 않다. 여행을 떠나기 전에 한동이는 모든 도시를 방문하는데 걸리는 최소의 시간을 알고싶어하는데, 한동이는 경영학과라 컴퓨터를 하지 못 하기 때문에 여러분이 한동이를 도와주자.
포항 시내의 도시들은 1부터 n까지 번호 지어져 있다. 한동이는 항상 포항시청에서 여행을 시작하고, 포항시청의 번호는 항상 1번이다. 모든 도시들은 양방향 도로로 연결되어있는데 한 도시에서 바로 길이 이어져있는 다른 도시로 이동하는데는 항상 1의 시간이 걸린다. 포항시청에서는 어떤 도시든지 갈 수 있다. 또한 포항의 도로는 굉장히 잘 되어있어서 도로끼리 사이클을 만들지 않는다.
여러분의 목표는 한동이가 모든 도시를 방문하는데 걸리는 최소의 시간을 출력하는 것이다.
입력
입력의 첫 줄에는 포항에 있는 도시의 숫자 n이 주어진다. 1 ≤ n ≤ 30,000.
다음 n-1줄에는 도시를 잇는 도로가 주어진다. 각 줄에는 정수 a와 b가 주어진다. 이는 a도시와 b도시를 잇는 도로가 존재한다는 의미이다. (1 ≤ a,b ≤ n; a≠b)
n+1번째 줄에는 정수 m이 주어지는데, 이는 한동이가 방문해야 할 도시의 숫자를 의미한다. 1 ≤ m ≤ 5,000 그 후 m개의 줄에는 한 줄에 하나씩 한동이가 방문해야 할 도시의 숫자가 순서대로 주어진다.
출력
첫 줄에 한동이가 방문해야 할 모든 도시를 방문 할 수 있는 최소 시간을 출력한다.
예제 입력 1
5 1 2 1 5 3 5 4 5 4 1 3 2 5
예제 출력 1
7
출처
Olympiad > Polish Olympiad in Informatics > POI 2001/2002 > Stage 1 2번
- 문제를 번역한 사람: jwg8679
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호