당신은 Grand Slime Auto라는 게임을 하고 있다. 당신은 Slime City의 마피아 단원이다.

Slime City는 0~N-1 으로 번호 매겨진 총 N개의 구역으로 나눠져 있다. 도시에는 몇 개의 도로가 있으며, 도로는 다른 두개의 구역을 연결한다. 도시에는 몇 개의 차가 있다. i번째 차는 cars[i] 구역에 있다. ( cars[]는 입력으로 주어짐 ) 한 구역에 여러 개의 차가 있을 수도 있다.

오늘날 당신은 보호금을 모으기 위해 몇 개의 상점을 돌 것이다.

당신은 어떤 순서로 돈을 모을지 결정 해났다. 이순서는 districts[]로 입력으로 주어진다. 당신은 0 -> districts[0] -> districts[1] -> ...순으로 방문한다. 같은 구역이 한 리스트에 여러 번 나타날 수도 있다. 당신은 맨 처음 구역 0에 있다고 가정한다.

Slime City에는 두개의 교통수단이 있다. 걷기와 운전하기.

• 걸어서 순회할 경우 이동시간은 (도로의 거리 * inverseWalkSpeed) 만큼 걸린다.
• 차로 순회할 경우 이동시간은 (도로의 거리 * inverseDriveSpeed) 만큼 걸린다.

그러나 Slime City의 차량 절도 벌금은 배우 높아서 차에서 내리는 순간, 그 차를 빼앗길 것이고 더 이상 타지 못할 것이다. 상점에 들어가 보호금을 모으기 위해서는 반드시 차에서 내려야 한다는 점을 명시해라.

돈을 모을 때에는 시간이 걸리지 않는다고 가정하며, 상점에서 모든 돈을 모으기 위한 최소 시간을 출력한다.

입력

• cars_N이 주어지고 (1 <= cars_N <= 50 ) cars[]가 주어진다. ( 0 <= cars[] <= N-1 )
• districts_N이 주어지고 ( 1 <= districts_N <= 50 ) districts[]가 주어진다. ( 0 <= districts[] <= N-1 ) districts[]에 연속적으로 두개의 같은 원소는 존재하지 않는다. 따라서 districts[0] 은 0이 아닐 것이다. ( 맨 처음 0에 있는 다고 가정했기 때문 )
• 도로의 개수인 N이 주어지고 ( 2 <= N <= 50 )
• N^2 table인 road[][]가 주어진다. ( 0 <= road[][] <= 62 ) 양방향 도로임으로 road[i][j] = road[j][i]이다. 그리고 road[i][j] == 0 이면 i에서 j로의 길이 없다는 뜻이며 1 <= road[i][j] <= 62 면 road[i][j]를 잇는 도로의 길이가 road[i][j]라는 뜻이다. Slime City는 연결되어 있으며, 따라서 어느 한 구역에서 다른 구역으로 무조건 몇 개의 도로를 거처 갈 수 있다.
• inverseWalkSpeed 가 입력으로 들어온다. ( 2 <= inverseWalkSpeed <= 100 )
• inverseDriveSpeed 가 입력으로 들어온다. ( 1 <= inverseDriveSpeed <= 99 ) inverseWalkSpeed 는 반드시 inverseDriveSpeed 보다 크다.

출력

입출력 예

입력 

1 1             // cars_N cars[]
3 2 3 0        // districts_N districts[]
4               // N
0 0 1 0        // road[][]
0 0 0 2
1 0 0 3
0 2 3 0
5  1             // inverseWalkSpeed inverseDriveSpeed

출력 

36

입출력 보충

 
설명 : 
1. 구역 0에서 구역 2로 걸어간다. ( 거리 1 )
2. 구역 2에서 구역 3로 걸어간다. ( 거리 3 )
3. 구역 3에서 구역 1로 걸어간다. ( 거리 2 )
4. 구역 1 -> 구역 3 -> 구역 2 -> 구역 0으로 차로 운전해간다. ( 거리 2 + 3 + 1 )

Mintime = 1 * 5 + 3 * 5 + 2 * 5 + (2 + 3 + 1) * 1 = 36

출처 : TopCoder
번역 : makesource