10713번 - 기차 여행
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 545 | 199 | 153 | 38.931% |
문제
JOI나라에는 N개의 도시가 있고, 각 도시에 1,2,...,N까지의 번호를 갖고 있다.
그리고, 철도가 N-1개 있고, 각 철도에 1,2,...N-1의 번호를 갖고 있다.
철도 i (1 ≦ i ≦ N − 1)는 도시 i과 도시 i+1을 양방향으로 연결시키는 철도를 의미한다.
JOI나라의 철도를 타는 방법에는, 티켓을 구입해 승차하는 방법과 IC카드로 승차하는 방법 두 가지가 존재한다.
- 철도 i에 티켓을 구입해 승차할 때는 Ai 원의 비용이 든다.
- 철도 i에 IC카드로 승차하는 경우에는 Bi 원의 비용이 든다. 하지만 IC카드로 철도를 탈 때는 IC카드를 미리 구입해둬야만 한다. 철도 i에서 쓸 수 있는 IC카드를 구입하는데는 Ci원의 비용이 든다. 한번 구입한 IC카드는 몇번이라도 사용할 수 있다.
IC카드가 처리가 간편하기 때문에, IC카드로 승차하는 방법의 운임이 티켓을 구입하는 경우보다 싸다. 즉, i = 1,2,...N-1일 때 Ai > Bi이다. IC카드는 철도마다 다르기 때문에, 철도 i에서 사용할 수 있는 카드는 다른 철도에서는 사용할 수 없다.
당신은 JOI나라를 여행하기로 마음먹었다. 도시 P1에서 출발해, P2,P3... ,PM 순서의 도시를 방문할 예정이다. 여행은 M-1일간 이루어진다. j일째 (1 ≦ j ≦ M − 1) 에 도시 Pj으로부터 Pj+1으로 이동한다. 이때, 여러 개의 철도를 타는 경우도 있고, 같은 도시를 여러 번 방문할 수도 있다. JOI나라의 철도는 빨라서 어느 도시도 하루만에 도착할 수 있다
당신은 현재 어느 철도의 IC카드도 갖고있지 않다. 당신은 미리 몇개의 IC카드를 구입해, 이 여행에서 사용되는 비용, 즉 IC카드를 구입하는 비용 + 철도를 타는 비용을 최소화하고 싶다.
JOI나라의 도시 수, 여행의 기간, 그리고 JOI나라의 철도 각각의 운임과, IC카드의 가격이 주어졌을 때, 여행의 비용을 최소화하는 프로그램을 작성하시오.
입력
표준 입력으로 아래의 항목들이 주어진다.
- 첫 번째 줄에서는 정수 N, M이 주어진다.
- 두 번째 줄에는 M개의 정수 P1,P2,...PM이 주어진다. j일째 (1 ≦ j ≦ M − 1) 에 도시 Pj에서 Pj+1로 이동하는 것을 의미한다.
- 3번째 줄부터 N-1개의 줄에는 (1 ≦ i ≦ N − 1) 3개의 정수 Ai, Bi, Ci가 주어진다. 각각 철도 i의 티켓을 구입하는 가격, 철도 i를 카드를 사용했을 때 통과하는 가격, IC카드를 구매하는 가격을 의미한다.
입력 데이터는 아래의 조건을 만족한다.
- 2 ≦ N ≦ 100 000．
- 2 ≦ M ≦ 100 000．
- 1 ≦ Bi < Ai ≦ 100 000 (1 ≦ i ≦ N − 1)．
- 1 ≦ Ci ≦ 100 000 (1 ≦ i ≦ N − 1)．
- 1 ≦ Pj ≦ N (1 ≦ j ≦ M)．
- Pj ≠ Pj+1 (1 ≦ j ≦ M − 1)．
출력
표준출력에 여행에 드는 최저 비용을 첫째 줄에 출력하시오.
예제 입력 1
4 4 1 3 2 4 120 90 100 110 50 80 250 70 130
예제 출력 1
550
예제 입력 2
8 5 7 5 3 5 4 12 5 8 16 2 1 3 1 5 17 12 17 19 7 5 12 2 19 4 1 3
예제 출력 2
81
힌트
위의 경우, 여행에 드는 비용이 최소가 되는 방법은 아래와 같다.
- 철도 2와 철도 3의 IC카드를 구입한다. 80+130 = 210원의 비용이 발생한다．
- 1일째에, 도시 1에서 도시 2까지 티켓을 사용해 이동하고, 도시 2에서 도시 3까지는 IC카드를 사용해 이동한다. 120+50= 170원의 비용이 발생한다.
- 2일째에, 도시 3에서 도시 2까지 IC카드를 사용해 이동한다. 50의 비용이 발생한다.
- 3일째에는 도시 2에서 도시 3까지 IC카드를 사용해 이동하고, 다음으로 도시 3에서 도시 4까지 IC카드를 사용해 이동한다. 50+70 = 120원을 사용한다.
이렇게 이동하면, 여행에 드는 비용의 합계는 210+170+50+120 = 550원이 된다. 이 비용이 최소이므로, 550을 출력한다.
© 2018 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 강남대로 359 대우도씨에빛2 5층 502호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: [email protected]
- 통신판매신고번호: 제 2017-서울서초-2193 호
