Untitled
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...