Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <limits.h>
- long long INF = LONG_LONG_MAX;
- int n, m, nS, nD, visited[10], taken[10], k[6][16], k_num;
- long long wS, wD, weights[10], answer;
- long long min(long long a, long long b) {
- return ((a < b) ? a : b);
- }
- void recursive(int x, int nS, int nD) {
- if(x == m) {
- long long result = 0;
- for(int i = 0; i < n; ++i) {
- memset(taken, 0, sizeof(taken));
- for(int j = 1; j <= k[i][0]; ++j) {
- if(!taken[visited[k[i][j]]]) {
- result += weights[visited[k[i][j]]];
- taken[visited[k[i][j]]] = 1;
- }
- }
- }
- answer = min(answer, result);
- return;
- }
- if(visited[x]) {
- recursive(x + 1, nS, nD);
- } else {
- if(nS) {
- ++k_num;
- weights[k_num] = wS;
- visited[x] = k_num;
- recursive(x + 1, nS - 1, nD);
- visited[x] = 0;
- --k_num;
- }
- if(nD) {
- for(int i = x + 1; i < m; ++i) {
- if(!visited[i]) {
- ++k_num;
- weights[k_num] = wD;
- visited[x] = visited[i] = k_num;
- recursive(x + 1, nS, nD - 1);
- --k_num;
- visited[i] = visited[x] = 0;
- }
- }
- }
- }
- }
- int main() {
- FILE *input = fopen("input.txt", "r");
- fscanf(input, "%d%d%d%d%lli%lli", &n, &m, &nS, &nD, &wS, &wD);
- for(int i = 0; i < n; ++i) {
- fscanf(input, "%d", &k[i][0]);
- for(int j = 1; j <= k[i][0]; ++j){
- fscanf(input, "%d", &k[i][j]);
- --k[i][j];
- }
- }
- fclose(input);
- memset(visited, 0, sizeof(visited));
- k_num = 0;
- answer = INF;
- recursive(0, nS, nD);
- FILE *output = fopen("output.txt", "w");
- fprintf(output, "%lli", answer);
- fclose(output);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement