#2415 지하철타고 슝슝

14  2 s   128 MB  

Description

영훈이는 지하철 노선을 제공하는 앱을 만들고 있습니다. 이 앱의 주요 기능 중 하나는 출발역과 도착역을 지정해서 가장 빠른 길의 소요 시간을 알려주는 것입니다. 영훈이는 앱 이용자들이 즐겨찾는 출발-도착역 쌍에 대해 미리 소요 시간을 계산해서 입력해두려고 합니다.

소요 시간은 출발-도착역 경로 상에서 열차의 이동 시간과 환승에 드는 시간의 합으로 계산됩니다.

숙제와 퀴즈로 바쁜 영훈이를 위해, 우리가 대신 이 기능을 구현해봅시다.

첫 번째 Sample Input을 표현한 지하철 노선도

Input

입력의 첫 줄에는 지하철 노선의 개수 $N$과 환승역의 개수 $M$, 그리고 앱 이용자들이 즐겨찾는 출발-도착역 쌍의 개수 $Q$가 공백 하나를 사이에 두고 주어집니다. $ (1 \leq N \leq 8, 0 \leq M \leq 60, 1 \leq Q \leq 150) $

그 다음 $2N$개의 줄에 $N$개의 노선 정보가 각각 두 줄로 주어집니다. 노선 정보의 첫 번째 줄에는 $i$번째 노선을 구성하는 역의 개수 $S_{i}$가 주어지고, 두 번째 줄에는 $S_{i}$개의 역 이름과 $S_{i} - 1$개의 역 사이 열차가 이동하는데 드는 소요 시간 $T_{ij}$가 번갈아가며 공백으로 구분되어 주어집니다. $(2 \leq S_{i} \leq 15, 1 \leq T_{ij} \leq 15, 1 \leq i \leq $N$, 1 \leq j < S_{i})$

그 다음 $M$개의 줄에 환승역의 이름과 해당 환승역에서 노선을 갈아타는 데에 드는 시간 $C_{i}$가 공백으로 구분되어 주어집니다. $(1 \leq C_{i} \leq 15, 1 \leq i \leq M)$

마지막으로 그 다음 $Q$개의 줄에 앱 이용자들이 즐겨찾는 출발-도착역 쌍이 한 줄에 한 쌍씩 주어집니다. 모든 역 이름은 15개 이하의 알파벳 소문자로 구성되고, 하나의 노선에는 같은 이름이 두 번 이상 등장하지 않습니다.

입력에 등장하는 모든 역 사이에는 적어도 하나 이상의 이동 가능한 경로가 존재합니다. 다시 말해서, 이동이 불가능한 경우는 없기 때문에 이를 고려하지 않고 문제를 풀어도 무방합니다. 입력으로 주어지는 모든 숫자는 정수입니다.

Output

$Q$개의 출발-도착역 쌍에 대해 한 줄에 하나씩 가장 빠른 길의 소요 시간을 출력합니다.

Sample Input

Sample Output

3 2 5
4
snuofedu 2 gangnam 2 yeoksam 2 seollueung
2
gangnam 3 yangjae
3
seonjeongneung 3 seollueung 2 hanti
gangnam 3
seollueung 1
hanti yangjae
gangnam seollueung
snuofedu hanti
yangjae snuofedu
yeoksam yeoksam
13
4
9
8
0

Sample Input 2

3 5 3
5
gloucester 1 kensington 3 knightsbridge 2 hydepark 3 greenpark
4
gloucester 3 kensington 3 sloanesquare 1 victoria
2
greenpark 5 victoria
greenpark 3
victoria 2
sloanesquare 2
kensington 1
gloucester 2
hydepark sloanesquare
greenpark sloanesquare
gloucester victoria

Sample Output 2
9
8
6

Source

SHAKE! 예선대회