Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.99 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <limits.h>
  4.  
  5. long long INF = LONG_LONG_MAX;
  6. int n, m, nS, nD, visited[10], taken[10], k[6][16], k_num;
  7. long long wS, wD, weights[10], answer;
  8.  
  9. long long min(long long a, long long b) {
  10. return ((a < b) ? a : b);
  11. }
  12.  
  13. void recursive(int x, int nS, int nD) {
  14. if(x == m) {
  15. long long result = 0;
  16. for(int i = 0; i < n; ++i) {
  17. memset(taken, 0, sizeof(taken));
  18. for(int j = 1; j <= k[i][0]; ++j) {
  19. if(!taken[visited[k[i][j]]]) {
  20. result += weights[visited[k[i][j]]];
  21. taken[visited[k[i][j]]] = 1;
  22. }
  23. }
  24. }
  25. answer = min(answer, result);
  26. return;
  27. }
  28. if(visited[x]) {
  29. recursive(x + 1, nS, nD);
  30. } else {
  31. if(nS) {
  32. ++k_num;
  33. weights[k_num] = wS;
  34. visited[x] = k_num;
  35. recursive(x + 1, nS - 1, nD);
  36. visited[x] = 0;
  37. --k_num;
  38. }
  39. if(nD) {
  40. for(int i = x + 1; i < m; ++i) {
  41. if(!visited[i]) {
  42. ++k_num;
  43. weights[k_num] = wD;
  44. visited[x] = visited[i] = k_num;
  45. recursive(x + 1, nS, nD - 1);
  46. --k_num;
  47. visited[i] = visited[x] = 0;
  48. }
  49. }
  50. }
  51. }
  52. }
  53.  
  54. int main() {
  55. FILE *input = fopen("input.txt", "r");
  56. fscanf(input, "%d%d%d%d%lli%lli", &n, &m, &nS, &nD, &wS, &wD);
  57. for(int i = 0; i < n; ++i) {
  58. fscanf(input, "%d", &k[i][0]);
  59. for(int j = 1; j <= k[i][0]; ++j){
  60. fscanf(input, "%d", &k[i][j]);
  61. --k[i][j];
  62. }
  63. }
  64. fclose(input);
  65. memset(visited, 0, sizeof(visited));
  66. k_num = 0;
  67. answer = INF;
  68. recursive(0, nS, nD);
  69. FILE *output = fopen("output.txt", "w");
  70. fprintf(output, "%lli", answer);
  71. fclose(output);
  72. return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement