APIO 2009 3번 ATM- 현금 인출기(ATM) > 문제은행 : 정보올림피아드&알고리즘




2423 : 현금 인출기(ATM)

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
9 회   
시도횟수
35 회   

문제

정올 도시는 모든 도로들이 일방통행으로 되어 있다. 

도로들이 만나는 모든 교차로에는 정올은행의 현금입출금기(ATM)가 설치되어 있다.

정올에는 유명한 레스토랑 체인인 인프론트 하우스가 있다. 이 레스토랑의 각 체인점들은 교차로에만 위치한다.

 

물론 각 교차로마다 항상 이 레스토랑 체인점이 있는 것은 아니다. 이 레스토랑은 현금만 사용할 수 있다. 

정올에 사는 경수는 오늘 오후에 이 레스토랑에서 가족들과 파티를 열려고 한다. 

그런데 갖고 있는 현금이 부족하여 레스토랑으로 가는 동안에 가능한 한 많은 현금을 ATM 기기로부터 인출할 계획을 세웠다. 

그는 자신의 집에서 출발하여 차로 이동하면서 통과하는 모든 교차로 ATM 기기에 들어있는 현금 전부를 인출하려고 한다. 

차량의 최종 목적지는 인프론트 하우스 체인점 중의 한 곳이고, 이 체인점이 어떤 교차로에 위치하는지는 상관없다.

 

경수는 정올은행의 홈페이지 정보를 통해 각 ATM 기기에 현금이 얼마나 들어 있는지를 알고 있다. 

이동 시 동일한 도로나 교차로를 여러 번 지날 수 있다. 

ATM 기기의 현금은 새로 보충되지 않기 때문에 첫 번째 이후 다시 방문하는 교차로의 ATM 기기에는 인출할 현금이 없다.

 

예를 들어, 아래 그림처럼 도시에 6개의 교차로가 있다고 하자. 교차로는 원으로 표시되어 있고, 화살표는 도로를 나타낸다. 

이중 원으로 표시된 교차로에는 레스토랑이 있다. 각 ATM 기기가 갖고있는 현금의 액수는 교차로 위에 표시된 숫자이다. 

이 예에서 현금 인출을 1번 교차로부터 시작한다면, 경수는 1-2-4-1-2-3-5의 경로를 통해서 총 47의 현금을 인출할 수 있다.


 


 

 

경수가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수가 얼마인지를 계산하는 프로그램을 작성하시오.

 


입력형식

첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다.

 

그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차로 번호와 끝 교차로 번호를 나타내는 2개의 정수가 주어진다.

 

그 다음 N개의 줄에는 1번 교차로부터 차례대로 각 교차로의 ATM 기기가 보유한 현금의 액수를 나타내는 정수가 각 줄에 하나씩 주어진다.

 

그 다음 줄에는 두 개의 정수 S와 P가 주어진다.

여기서 S는 출발 장소(현금 인출의 시작 장소)인 교차로 번호이고 P는 레스토랑의 개수이다(1≤P≤N).

 

그 다음 줄에는 각 레스토랑이 있는 교차로의 번호를 나열한 P개의 정수가 주어진다.

 

N, M≤500,000 이고, 각 ATM 기기에 들어 있는 현금의 액수는 0 이상 4,000 이하이다. 모든 입력에서 경로의 출발 장소로부터 일방통행 도로를 통해 도달 가능한 레스토랑이 항상 하나 이상 존재한다.


출력형식

출력은 한 개의 정수이다. 이 정수는 경수가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수이다.

입력 예

6 7 
1 2 
2 3 
3 5 
2 4 
4 1 
2 6 
6 5 
10 
12 
8 
16 
1 
5 
1 4 
4 3 5 6

출력 예

47

Hint!

강연결 요소 : Kosaraju's Alogirhtm



SCC, Tarjan, Kosaraju

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP