Advertisement
Guest User

Untitled

a guest
Feb 20th, 2017
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.78 KB | None | 0 0
  1. //: CCC2010S4.cpp
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int dist[102];
  6. int dist1[102];
  7.  
  8. struct cmp {
  9. bool operator() (const int& a, const int& b) {
  10. if(dist[a] == dist[b]) {
  11. return a < b;
  12. }
  13. else {
  14. return dist[a] < dist[b];
  15. }
  16. }
  17. };
  18. struct cmp1 {
  19. bool operator() (const int& a, const int& b) {
  20. if(dist1[a] == dist1[b]) {
  21. return a < b;
  22. }
  23. else {
  24. return dist1[a] < dist1[b];
  25. }
  26. }
  27. };
  28.  
  29. int M;
  30. int ep;
  31. int corner;
  32. int cost;
  33. vector<int> v;
  34. pair<int, int> edges[1002][1002];
  35. int infinity = 1000000000;
  36. set<int> G[102];
  37. int C[102][102];
  38. set<int, cmp> s;
  39. set<int, cmp1> s1;
  40. int ans = 0;
  41. int ans1 = 0;
  42. int main() {
  43. for(int i=0; i<102; i++) {
  44. for(int j=0; j<102; j++) {
  45. C[i][j] = infinity;
  46. }
  47. }
  48. cin >> M;
  49. for(int i=1; i<=M; i++) {
  50. cin >> ep;
  51. for(int j=0; j<ep; j++) {
  52. cin >> corner;
  53. v.push_back(corner);
  54. }
  55. for(int j=0; j<ep; j++) {
  56. cin >> cost;
  57. if(edges[v[j]][v[(j+1)%ep]].first == 0) {
  58. edges[v[j]][v[(j+1)%ep]] = make_pair(cost, i);
  59. edges[v[(j+1)%ep]][v[j]] = make_pair(cost, i);
  60. }
  61. else {
  62. G[i].insert(edges[v[j]][v[(j+1)%ep]].second);
  63. G[edges[v[j]][v[(j+1)%ep]].second].insert(i);
  64. C[edges[v[j]][v[(j+1)%ep]].second][i] = cost;
  65. C[i][edges[v[j]][v[(j+1)%ep]].second] = cost;
  66. edges[v[j]][v[(j+1)%ep]] = make_pair(infinity, i);
  67. edges[v[(j+1)%ep]][v[j]] = make_pair(infinity, i);
  68. }
  69. }
  70. v.clear();
  71. }
  72. for(int i=0; i<1002; i++) {
  73. for(int j=0; j<1002; j++) {
  74. if(edges[i][j].first != infinity && edges[i][j].first != 0) {
  75. G[M+1].insert(edges[i][j].second);
  76. G[edges[i][j].second].insert(M);
  77. if(edges[i][j].first < C[M+1][edges[i][j].second]) {
  78. C[M+1][edges[i][j].second] = edges[i][j].first;
  79. C[edges[i][j].second][M+1] = edges[i][j].first;
  80. }
  81. }
  82. }
  83. }
  84. for(int i=1; i<M+1; i++) {
  85. dist[i] = infinity;
  86. }
  87. dist[1] = 0;
  88. s.insert(1);
  89. while(! s.empty()) {
  90. int v = *s.begin();
  91. s.erase(s.begin());
  92.  
  93. for(set<int>::iterator it = G[v].begin(); it != G[v].end(); it++) {
  94. if(C[v][*it] < dist[*it] && *it != M+1) {
  95. s.erase(*it);
  96. dist[*it] = C[v][*it];
  97. s.insert(*it);
  98. }
  99. }
  100. }
  101. for(int i=1; i<=M+1; i++) {
  102. dist1[i] = infinity;
  103. }
  104. dist1[1] = 0;
  105. s1.insert(1);
  106. while(! s1.empty()) {
  107. int v = *s1.begin();
  108. s1.erase(s1.begin());
  109.  
  110. for(set<int>::iterator it = G[v].begin(); it != G[v].end(); it++) {
  111. if(C[v][*it] < dist1[*it]) {
  112. s1.erase(*it);
  113. dist1[*it] = C[v][*it];
  114. s1.insert(*it);
  115. }
  116. }
  117. }
  118. for(int i=1; i<=M; i++) {
  119. if(dist[i] != infinity) {
  120. ans = ans + dist[i];
  121. }
  122. }
  123. for(int i=1; i<=M+1; i++) {
  124. if(dist1[i] != infinity) {
  125. ans1 = ans1 + dist1[i];
  126. }
  127. }
  128. ans = min(ans, ans1);
  129. cout << ans << endl;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement