시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB30181555.556%

문제

강호는 구역 N개로 나누어져 있는 도시의 건물주이다. 각각의 구역은 양방향 도로로 이루어져 연결되어져 있다. 각 구역은 0번부터 N-1번까지 번호가 매겨져 있다.

강호는 차를 C대 가지고 있고, 각각의 차는 구역 중 하나에 주차되어 있다. 한 구역에 여러 대의 차가 주차되어 있을 수도 있다. 

오늘은 월세를 받는 날이다. 강호는 직접 자신의 건물을 돌아다니면서 월세를 받으려고 한다. 월세를 받아야 하는 건물은 총 M개가 있으며, 월세를 받는 순서는 Ai로 미리 정해져 있다. 즉, 첫 번째로 A0 구역으로 가서 월세를 받고, 그 다음 A1 구역으로 가서 월세를 받고, ..., 마지막으로 AM-1구역으로 가서 월세를 받아야 한다. 강호는 처음에 0번 구역에 있다.

구역을 이동하는 방법은 걷기와 차 타기 두 가지가 있다. 걷는데 걸리는 시간은 W × 도로의 길이 이며, 차를 타고 이동하는데 걸리는 시간은 D × 도로의 길이이다.

강호가 자신의 차가 주차되어있는 구역에 도착했다면, 차 한 대에 탑승해서 원하는 곳으로 이동할 수 있다. 강호는 한 번 차에서 내린 다음에는 다시는 그 차를 타지 않는다. 또, 월세를 받을 때는 반드시 차에서 내려야 한다.

도로의 정보가 주어졌을 때, 월세를 모두 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N과 주차되어 있는 차의 개수 C, 월세를 받아야 하는 건물의 개수 M, 걷는데 걸리는 시간 W, 차를 타고 이동하는데 걸리는 시간 D가 주어진다. (1 ≤ N, C, M ≤ 50, 1 ≤ D < W ≤ 100)

둘째 줄에는 차가 주차되어 있는 구역이 공백으로 구분해서 주어진다.

셋째 줄에는 월세를 받아야하는 순서 Ai가 공백으로 구분해서 주어진다. (A0 ≠ 0)

넷째 줄부터 N개의 줄에는 도시의 도로 정보가 인접 행렬 형식으로 주어진다. i번 줄의 j번째 수는 i번 구역과 j번 구역의 도로 정보를 나타내며, 0인 경우에는 도로가 없는 것, 자연수인 경우에는 그 도로의 길이이다. 도로의 길이는 62를 넘지 않는 자연수이다.

도로는 양방향 도로이기 때문에, i번째 줄의 j번째 수와 j번째 줄의 i번째 수는 항상 같으며, i번째 줄의 i번째 수는 항상 0이다. 또, 이동할 수 없는 구역은 없다.

출력

첫째 줄에 월세를 모두 받는데 걸리는 시간의 최솟값을 출력한다.

예제 입력 1

4 1 3 5 1
1
2 3 0
0 0 1 0
0 0 0 2
1 0 0 3
0 2 3 0

예제 출력 1

36

예제 입력 2

3 1 2 2 1
1
2 0
0 37 0
37 0 38
0 38 0

예제 출력 2

262

예제 입력 3

3 2 3 3 1
2 2
1 2 1
0 11 5
11 0 0
5 0 0

예제 출력 3

95

예제 입력 4

3 1 2 2 1
1
2 0
0 38 0
38 0 37
0 37 0

예제 출력 4

262

예제 입력 5

6 4 5 53 37
2 5 1 2
1 5 1 2 4
0 2 3 0 5 0
2 0 0 0 0 8
3 0 0 4 0 0
0 0 4 0 0 6
5 0 0 0 0 0
0 8 0 6 0 0

예제 출력 5

1259

힌트

예제 1의 경우에 구역 0에서 구역 2까지 걸어간 다음, 월세를 받는다. 그 다음 구역 2에서 3으로 걸어가서 다시 월세를 받는다. 구역 1로 걸어간 다음, 차를 타고 구역 0으로 가서 월세를 받는다.

총 걸린 시간은 5×1 + 5×3 + 5×2 + 1×2 + 1×3 + 1×1 = 36 이다.

예제 2의 경우에 구역 0에서 구역 1로 걸어간다. 그 다음 거기서 차를 타고 구역 2로 이동한다. 차에서 내려서 월세를 받은 다음에 구역 2에서 1로, 그리고 0으로 걸어서 이동한다. 이제 구역 0에서 월세를 받으면 된다.

총 걸린 시간은 37×2 + 38×1 + 38×2 + 37×2 = 262 이다.

출처