Untitled

 avatar
unknown
plain_text
2 years ago
1.4 kB
4
Indexable
#include<iostream>

using namespace std;

int N;
int arrPrice[21];
int M;
int arrPacket[60][60];
int L;
int arrLinhKienCan[21];
int visitedLK[60];
int visitedPacket[60];
int minPrice = 100000;
void BT(int cnt, int packet, int sumPrice) {
if (cnt == L) {
if (sumPrice < minPrice) {
minPrice = sumPrice;
}
return;
}
visitedPacket[packet] = 1;
for (int i = 1; i <= N + M; i++)
{
if (arrPacket[i][arrLinhKienCan[cnt]] == 1 && visitedPacket[i] == 0) {
BT(cnt+1 , i, sumPrice + arrPacket[i][0]);
//visitedLK[arrLinhKienCan[cnt]] = 1;
}
else if (arrPacket[i][arrLinhKienCan[cnt]] == 1 && visitedPacket[i] == 1) {
BT(cnt + 1, i, sumPrice);
}
}
visitedPacket[packet] = 0;
}
 
int main() {
freopen("input.txt", "r", stdin);
int T;
cin >> T;
int temp;
int lk;
for (int tc = 1; tc <= T; tc++)
{
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> arrPrice[i];
}
cin >> M;
for (int i = 1; i <= M; i++)
{
cin >> arrPacket[i][0];
cin >> temp;
for (int j = 1; j <= temp; j++)
{
cin >> lk;
arrPacket[i][lk] = 1;
}
}
cin >> L;
for (int i = 0; i < L; i++)
{
cin >> arrLinhKienCan[i];
}
for (int i = M + 1; i <= M + N; i++)
{
arrPacket[i][0] = arrPrice[i - M];
arrPacket[i][i - M] = 1;
}
for (int i = 0; i <= M + N; i++)
{
visitedLK[i] = 0;
visitedPacket[i] = 0;
}
minPrice = 100000;
BT(0, 0, 0);
cout << "#"<< tc << " " << minPrice << endl;
}
return 0;
}
Editor is loading...