Advertisement
pdaogu

Untitled

Dec 19th, 2019
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. #define MAX 250000
  7. #define INF 100000009
  8.  
  9. std::vector<int> A[MAX];
  10. std::vector<int> c[MAX];
  11. int n, m;
  12. int s[105], K;
  13.  
  14. int d[105][10005]; // key
  15. int node[105][10005]; // gia tri node
  16. int idx[105][10005]; // index cua node tuong ung trong array
  17. int sH; // size of array
  18. bool fixed[105][10005];
  19. int iS;
  20. int result;
  21.  
  22.  
  23. void output () {
  24. printf("%d\n", result);
  25. }
  26.  
  27. void swap(int i, int j) {
  28. int tmp = node[iS][i];
  29. node[iS][i] = node[iS][j];
  30. node[iS][j] = tmp;
  31. idx[iS][node[iS][i]]=i;
  32. idx[iS][node[iS][j]]=j;
  33. }
  34.  
  35. void upHeap(int i) {
  36. if(i == 0) return;
  37. while(i > 0) {
  38. int pi = (i-1)/2;
  39. if(d[iS][node[iS][i]] < d[iS][node[iS][pi]]) {
  40. swap(i,pi);
  41. }
  42. else {
  43. break;
  44. }
  45. i = pi;
  46. }
  47. }
  48.  
  49. void downHeap(int i) {
  50. int L = 2*i + 1;
  51. int R = 2*i + 2;
  52. int maxIdx = i;
  53. if(L < sH && d[iS][node[iS][L]] < d[iS][node[iS][maxIdx]]) maxIdx = L;
  54. if(R < sH && d[iS][node[iS][R]] < d[iS][node[iS][maxIdx]]) maxIdx = R;
  55. if(maxIdx != i) {
  56. swap(i, maxIdx);
  57. downHeap(maxIdx);
  58. }
  59. }
  60.  
  61. void insert(int v, int k) {
  62. d[iS][v] = k;
  63. node[iS][sH] = v;
  64. idx[iS][node[iS][sH]] = sH;
  65. upHeap(sH);
  66. sH++;
  67. }
  68.  
  69. bool inHeap(int v) {
  70. if(idx[iS][v] >= 0) return true;
  71. else return false;
  72. }
  73.  
  74. void updateKey(int v, int k) {
  75. if(d[iS][v] > k) {
  76. d[iS][v] = k;
  77. upHeap(idx[iS][v]);
  78. }
  79. else {
  80. d[iS][v] = k;
  81. downHeap(idx[iS][v]);
  82. }
  83. }
  84.  
  85. int deleteMin() {
  86. int sel_node = node[iS][0];
  87. swap(0, sH-1);
  88. sH--;
  89. downHeap(0);
  90. return sel_node;
  91. }
  92.  
  93. void dijkstra (int x) {
  94. sH = 0;
  95. for(int v=1; v <= n; ++v) {
  96. fixed[iS][v] = false;
  97. idx[iS][v] = -1;
  98. }
  99. d[iS][x] = 0;
  100. fixed[iS][x] = true;
  101. for(int i=0; i < A[x].size(); ++i) {
  102. int v = A[x][i];
  103. insert(v,c[x][i]);
  104. }
  105. while(sH > 0) {
  106. int u = deleteMin();
  107. fixed[iS][u] = true;
  108. for(int i=0; i < A[u].size(); ++i) {
  109. int v = A[u][i];
  110. if(fixed[iS][v]) continue;
  111. if(!inHeap(v)) {
  112. int w = d[iS][u] + c[u][i];
  113. insert(v,w);
  114. }
  115. else {
  116. if(d[iS][v] > d[iS][u] + c[u][i])
  117. updateKey(v, d[iS][u] + c[u][i]);
  118. }
  119. }
  120. }
  121. }
  122.  
  123. void solve() {
  124. memset(d, 0, sizeof(d));
  125. memset(node, 0, sizeof(node));
  126. memset(idx, 0, sizeof(idx));
  127. memset(fixed, 0, sizeof(fixed));
  128. iS = 1;
  129. for (int i = 1; i <= K; ++i) {
  130. dijkstra(s[i]);
  131. ++iS;
  132. }
  133. result = -INF;
  134. for (int i = 1; i <= K-1; ++i) {
  135. for (int j = i + 1; j <= K; ++j) {
  136. if (result < d[i][s[j]])
  137. result = d[i][s[j]];
  138. }
  139. }
  140. }
  141.  
  142. void input() {
  143. scanf("%d%d", &n, &m);
  144. int u,v,w;
  145. for(int i=1; i <= m; i++) { // Take Edges
  146. scanf("%d%d%d", &u, &v, &w);
  147. A[u].push_back(v);
  148. A[v].push_back(u);
  149. c[u].push_back(w);
  150. c[v].push_back(w);
  151. }
  152. scanf("%d", &K);
  153. for (int i = 1; i <= K; ++i) {
  154. scanf("%d", &s[i]);
  155. }
  156. }
  157.  
  158. // Driver code
  159. int main() {
  160. // freopen("inp", "r", stdin);
  161. // freopen("out", "w", stdout);
  162.  
  163. input();
  164. solve();
  165. output();
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement