문제
재우는 정올국에 배낭 여행을 왔다.
정올국은 N개의 도시로 이루어져 있고, 그 사이를 연결하는 기차 선로가 M개 있다.
각 기차 선로는 단방향이며, i번째 기차는 Ui번 도시에서 시작해서 Vi번 도시로 Ti분만에 이동한다.
재우는 기차 여행은 좋아하지만, 기차 환승은 그다지 좋아하지 않는다.
호구(?)와트로 가겠다고 킹크로스역에서 내려 플랫폼 9 3/4 벽에 냅다 부딪힌 경험이 있기 때문이다.
따라서 재우는 서로 다른 기차 선로는 최대 K개까지만 이용하려 한다.
또 재우는 철저히 계획적인 여행가이기 때문에, Q개의 여행 계획에 대해 미리 최적의 기차 노선을 알아보려 한다.
j번째 여행 계획은 시작 도시 Cj에서 Dj로 이동하는 것으로,
최적의 기차 노선은 주어진 조건을 만족하면서 이동 시간이 최소인 것이다.
만약 주어진 조건을 만족하면서 두 도시 사이를 이동할 수 없을 때에는, 계획을 파기한다.
재우가 여행 준비로 너무 바쁘다.
재우를 위하여 각 여행 계획에 대해 이동할 수 있는지 알아보고, 이동할 수 있다면 최적의 이동 시간을 구해주자.
이쯤 되면 재우는 분명 "쌤 저는 그럼 이문제 안풀어도 되나요?" 라고 할 것이다.
천만에 말씀 만만에 콩떡이다.
누군가 구해준다는 보장이 없을 뿐만 아니라
구해준 값이 맞는지 알 수 없기 때문이다. ^^
입력
첫 줄에 도시의 개수 N(2 ≤ N ≤ 70)과 기차 노선의 개수 M(1 ≤ M ≤ 106)이 주어진다.
둘째 줄부터 M개의 줄에 걸쳐 각 노선을 나타내는 정수 Ui, Vi, Ti(1 ≤ Ui, Vi ≤ N, 1 ≤ Ti ≤ 106)가 주어진다.
M+2번째 줄에는 K(1 ≤ K ≤ 109)와 여행 계획의 개수 Q(1 ≤ Q ≤ N<2)가 주어진다.
그 이후 Q개의 줄에 걸쳐 각 여행 계획을 나타내는 정수 Cj, Dj (1 ≤ Cj, Dj ≤ N)가 주어진다.
출력
Q개의 줄에 걸쳐 각 여행 계획에 대해 최적의 이동 시간을, 이동할 수 없다면 -1을 한 줄에 하나씩 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 11점 | K <= N <=7 |
| #2 | 11점 | k <= 3 |
| #3 | 17점 | K <= N |
| #4 | 61점 | 제한없음 |
예제1
47
121
1410
231
245
322
341
432
13
14
42
33
10
-1
0
예제2
47
121
1410
231
245
322
341
432
23
14
42
33
6
4
0
예제3
47
121
1410
231
245
322
341
432
33
14
42
33
3
4
0