철도망 확장

시간 제한1초메모리 제한128 MB

요약
연결된 철도망과 최대 10개의 가격이 있는 확장 노선, 승객 수요 행렬이 주어질 때, 예산 안에서 모든 승객의 총 이동 시간을 가장 많이 줄이는 부분집합을 고른다. With only up to 10 proposed routes, the primary technique is brute-force enumeration of all 2^p subsets, and for each subset run BFS or Floyd-Warshall on the resulting graph to compute all-pairs shortest paths and the total weighted travel time. The difficulty comes from combining exponential subset search with repeated shortest-path computation on an n<=50 graph and carefully evaluating the reduction against the baseline network. This is a heavy implementation and optimization problem typical of ICPC,
난이도

보통10점 중 7점

유형
그래프, 완전 탐색, 최단 경로, 구현
정답자
아직 제출이 없습니다

문제

어느 도시가 대중교통 철도망을 확장하려고 합니다. 여러 개의 확장 노선이 후보로 논의되고 있지만 예산이 한정되어 있어 일부만 건설할 수 있습니다. 예산을 넘지 않는 범위에서 후보 노선의 부분집합을 골라, 모든 승객의 총 이동 시간을 최대한 줄이는 것이 목표입니다.

현재 철도망과 최대 10개의 확장 후보 노선이 주어집니다. 가격의 합이 예산을 넘지 않는 후보 노선의 부분집합을 선택하여, 전체 승객의 총 이동 시간이 줄어드는 양을 최대로 만드세요.

이동 시간 규칙: 같은 노선에서 인접한 두 역 사이를 이동하는 데 정확히 1분이 걸리고, 한 역에서 다른 노선으로 갈아타는 데는 시간이 들지 않습니다. 모든 노선은 양방향으로 이용할 수 있습니다. 확장 전에도 현재 철도망은 이미 연결되어 있어 어떤 역에서든 다른 모든 역으로 갈 수 있습니다. 따라서 두 역 사이의 이동 시간은 두 역을 잇는 최소 역 간 이동 횟수(홉 수)와 같습니다.

입력

첫 번째 줄에 데이터 집합의 개수 KK가 주어집니다. 이어서 각 데이터 집합이 다음 형식으로 주어집니다.

  • 첫 줄에 네 정수 nn, mm, pp, BB가 주어집니다. nn은 역의 수(2≤n≤502 \le n \le 50), mm은 현재 노선의 수(1≤m≤501 \le m \le 50), pp는 확장 후보 노선의 수(1≤p≤101 \le p \le 10), BB는 총 예산입니다.
  • 다음 mm개의 줄은 각각 현재 노선 하나를 나타냅니다. 한 줄에는 그 노선이 지나는 역들을 순서대로 나열한 ni≥2n_i \ge 2개의 정수가 들어 있습니다.
  • 다음 pp개의 줄은 각각 확장 후보 노선 jj 하나를 나타냅니다. 각 줄은 노선의 가격 pjp_j 하나로 시작하고, 이어서 그 노선이 지나는 역들을 순서대로 나열한 nj′≥2n'_j \ge 2개의 정수가 옵니다.
  • 마지막으로 nn개의 줄이 주어지며, 각 줄에는 nn개의 정수가 있습니다. ii번째 줄의 jj번째 정수는 역 ii에서 역 jj로 가려는 승객의 수입니다.

역의 번호는 11부터 nn까지입니다.

출력

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력합니다. 여기서 xx는 데이터 집합의 번호이며 11부터 시작합니다. 다음 줄에는 정수 하나를 출력합니다. 가격의 합이 예산을 넘지 않는 후보 노선의 부분집합을 건설했을 때, 모든 승객의 총 이동 시간 합을 줄일 수 있는 최댓값입니다.

예제5

  1. 예제 1

    입력
    1
6 1 3 5
1 2 3 4 5 6
3 1 3
3 4 2
4 2 6
0 0 2 5 0 10
10 0 6 5 20 2
2 8 0 7 9 10
3 2 5 0 5 1
6 6 17 2 0 12
0 1 4 12 7 0
    예상 출력
    Data Set 1:
85

  2. 예제 2

    입력
    1
3 1 2 0
1 2 3
5 1 3
7 1 2
0 5 10
5 0 3
2 8 0
    예상 출력
    Data Set 1:
0

  3. 예제 3

    입력
    1
4 1 1 2
1 2 3 4
2 1 4
0 1 1 10
1 0 1 1
1 1 0 1
20 1 1 0
    예상 출력
    Data Set 1:
60

  4. 예제 4

    입력
    1
4 1 2 2
1 2 3 4
5 1 4
2 2 4
0 1 1 5
1 0 1 8
1 1 0 1
5 8 1 0
    예상 출력
    Data Set 1:
26

  5. 예제 5

    입력
    2
6 1 3 5
1 2 3 4 5 6
3 1 3
3 4 2
4 2 6
0 0 2 5 0 10
10 0 6 5 20 2
2 8 0 7 9 10
3 2 5 0 5 1
6 6 17 2 0 12
0 1 4 12 7 0
3 1 1 0
1 2 3
5 1 3
0 5 10
5 0 3
2 8 0
    예상 출력
    Data Set 1:
85
Data Set 2:
0