cinador   3년 전

문제

하루가 H시간인 나라에 살고 있는 A는 한 기타리스트의 열렬한 팬이다. 이번 여름에 A는 A가 사는 지역에서 멀리 떨어져 있는 곳에서 열리는 기타리스트의 콘서트를 보러 가려고 한다. 교통비가 많이 들까봐 걱정이 된 A는, 여러 정보를 찾아보다가 JAG라는 철도공사에서 값싸게 판매하고 있는 "1Day 패스" 라는 것을 알게 되었다.

JAG (Journey Administrative Group) 는 이 나라에 있는 여러 개의 철도회사를 총괄하고 있는 조직이다. JAG는 전국의 철도역 중 일부를 소유하고 있고, 그 역들을 이어주는 노선이 존재한다. 각 노선은 JAG에 소속하는 회사 중 하나가 관리하고 있고, 2개의 역을 중간에 정차하는 역 없이 양방향으로 이어준다. 또한, 각 노선에는 이용하는 데에 드는 비용과 걸리는 시간이 정해져 있고, 이들은 이 노선에서 어느 방향으로 출발해도 동일하다. JAG가 소유하고 있는 역들은 열차 시간표와 승강장이 매우 정교하게 설계되어 있어서, 임의의 역에 도착해서 내리면 대기 시간 없이 그 역에서 출발하는 노선에 타서 곧바로 출발할 수 있다. 

1Day 패스는 JAG가 경영난에서 벗어나기 위해서 발매하기 시작한 패스이다. JAG는 여러 종류의 1Day 패스를 팔고 있으며, 각 패스는 JAG가 지정한 가격으로 구매할 수 있다. 또한, 패스에는 JAG에 소속한 회사 이름 몇 개가 적혀있는데, 이 회사들이 관리하고 있는 노선을 하루동안 추가 요금 없이 무제한으로 탈 수 있다. 1Day 패스는 여러 장 구매할 수 있으며, 이 경우에는 여러 개의 패스에 적혀있는 모든 회사가 관리하는 노선을 이용할 때 혜택을 받을 수 있다. 단, 패스에 적혀있지 않은 회사가 관리하고 있는 노선을 이용할 때는 그 노선의 비용을 지불해야 한다.

A는 이 1Day 패스를 적절히 이용하여 최소비용으로 콘서트장에서 가장 가까운 역까지 이동하려고 한다. 또한, 1Day 패스의 유효기간은 하루이기 때문에 이 나라의 하루에 해당하는 H시간 이내에는 원하는 역에 도착하려고 한다. 

JAG가 소유하고 있는 역들의 노선 정보와 1Day 패스의 정보가 주어질 때, A가 출발하는 역에서 도착하려고 하는 역까지 H시간 이내로 도달하는 데에 필요한 비용(노선 이용 비용과 1Day 패스 구매 가격의 합)의 최솟값을 구하여라. 만약 H시간 이내에 도착할 수 없거나, 도착하려고 하는 역까지 가는 경로가 없을 경우에는 -1을 출력한다.

ㅤ

입력

입력은 150개 이하의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.

preview

우선 JAG가 소유하는 역들의 노선 정보가 주어진다. N (2 ≤ N ≤ 100) 은 역의 개수, M (1 ≤ M ≤ 500) 은 노선의 수, H (1 ≤ H ≤ 24) 는 A가 살고 있는 나라의 하루에 해당하는 시간, K (1 ≤ K ≤ 8) 는 JAG에 소속하고 있는 철도회사의 수이다. 각 역은 1부터 N까지의 번호가 붙어있고, 각 회사는 1부터 K까지의 번호가 붙어있다. 

다음 M줄에는 노선 정보가 주어진다. ai 와 bi (1 ≤ ai < bi ≤ N) 는 i번째 노선이 이어주는 두 개의 역이다. ci (1 ≤ ci ≤ 10,000) 는 i번째 노선을 이용하는 데에 드는 비용을, hi (1 ≤ hi ≤ H) 는 걸리는 시간을, ri (1 ≤ ri ≤ K) 는 노선을 관리하는 회사를 나타낸다. 특정 두 역을 잇는 노선은 2개 이상 존재하지 않는다.

다음 줄에는 A가 출발하는 역인 S와 콘서트장에서 가장 가까운 역인 T가 주어진다 (1 ≤ S,T ≤ N). S와 T는 서로 다르다.

다음 줄부터는 1Day 패스의 정보가 주어진다. 우선, 1Day 패스의 종류 수에 해당하는 P (0 ≤ P ≤ 2K -1) 가 주어진다. 다음 P줄에는 각 1Day 패스의 정보가 한 줄에 하나씩 주어진다. lj (1 ≤ lj ≤ K) 와 dj (1 ≤ dj ≤ 10,000) 는 각각 j번째 1Day 패스에 적혀있는 회사의 수와 패스 구매 가격을 나타낸다. 같은 줄에, j번째 1Day 패스에 적혀있는 lj개의 회사번호 kj,1, kj,2, ... , kj,lj (1 ≤ kj,1 < kj,2 < ... < kj,lj  ≤ K) 가 주어진다. 특정 회사 조합을 갖는 1Day 패스는 2개 이상 존재하지 않는다.

입력으로 주어지는 모든 수는 정수이다.

입력의 마지막에는 0이 4개 주어진다. 이 입력이 주어지면 프로그램을 종료해야 한다. 

ㅤ

출력

각 테스트 케이스에 대해, 정답을 한 줄에 하나씩 출력한다. 즉, A가 출발하는 역에서 도착하려는 역까지 H시간 이내에 도달할 수 있다면 최소 비용을, 도달할 수 없다면 -1을 출력한다.

댓글을 작성하려면 로그인해야 합니다.