Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <unordered_set>
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7. #define vi vector <int>
  8. #define pb(a) push_back(a)
  9. #define all(v) v.begin(), v.end()
  10. #define pii pair <int, int>
  11. #define mp(a, b) make_pair(a, b)
  12.  
  13. const int INF = 1e9 + 9;
  14. const int MAXN = 1e6 + 2;
  15.  
  16. int n, m, k, q;
  17. vector <vector <pii> > g, gt;
  18. vector <vi> d;
  19. vi used, hubs;
  20.  
  21. signed main() {
  22. ios_base::sync_with_stdio(false);
  23. cin.tie(0);
  24.  
  25. cin >> n >> m >> k >> q;
  26. g.resize(n);
  27. gt.resize(n);
  28. used.resize(n, 0);
  29. hubs.resize(k, 0);
  30. d.resize(k, vi(k, INF));
  31. for (int i = 0; i < m; ++i) {
  32. int u, v, cost;
  33. cin >> u >> v >> cost;
  34. g[u - 1].pb(mp(v - 1, cost));
  35. gt[v - 1].pb(mp(u - 1, cost));
  36. }
  37. for (int i = 0; i < k; ++i) {
  38. cin >> hubs[i];
  39. hubs[i]--;
  40. }
  41. vi ishub(n);
  42. for (int i = 0; i < k; ++i)
  43. ishub[hubs[i]] = 1;
  44. vector <vi> d(k, vi(n, INF)), dt(k, vi(n, INF));
  45. for (int i = 0; i < k; ++i){
  46. d[i][hubs[i]] = 0;
  47. set <pii> s;
  48. s.insert({0, hubs[i]});
  49. while (!s.empty()){
  50. auto v = *s.begin();
  51. s.erase(s.begin());
  52. for (auto to : g[v.second]){
  53. if (d[i][v.second] + to.second < d[i][to.first]){
  54. s.erase({ d[i][to.first], to.first });
  55. d[i][to.first] = d[i][v.second] + to.second;
  56. s.insert({ d[i][to.first], to.first });
  57. }
  58. }
  59. }
  60. }
  61. for (int i = 0; i < k; ++i){
  62. dt[i][hubs[i]] = 0;
  63. set <pii> s;
  64. s.insert({ 0, hubs[i] });
  65. while (!s.empty()){
  66. auto v = *s.begin();
  67. s.erase(s.begin());
  68. for (auto to : gt[v.second]){
  69. if (dt[i][v.second] + to.second < dt[i][to.first]){
  70. s.erase({ dt[i][to.first], to.first });
  71. dt[i][to.first] = dt[i][v.second] + to.second;
  72. s.insert({ dt[i][to.first], to.first });
  73. }
  74. }
  75. }
  76. }
  77. int cnt = 0, ans = 0;
  78. for (int j = 0; j < q; ++j){
  79. int u, v;
  80. cin >> u >> v;
  81. --u, --v;
  82. if (u == v){
  83. ++cnt;
  84. }
  85. else{
  86. int uis = -1, vis = -1;
  87. for (int i = 0; i < k; ++i){
  88. if (hubs[i] == u)
  89. uis = i;
  90. if (hubs[i] == v)
  91. vis = i;
  92. }
  93. if (uis != -1 && vis != -1){
  94. if (d[uis][v] < INF){
  95. ++cnt;
  96. ans += d[uis][v];
  97. }
  98. }
  99. else if (uis != -1){
  100. if (d[uis][v] < INF){
  101. ++cnt;
  102. ans += d[uis][v];
  103. }
  104. }
  105. else if (vis != -1){
  106. int mini = INF;
  107. for (int cur = 0; cur < k; ++cur){
  108. if (d[cur][v] < INF)
  109. mini = min(mini, d[cur][v]);
  110. }
  111. if (mini < INF){
  112. ++cnt;
  113. ans += mini;
  114. }
  115. }
  116. else{
  117. int mini = INF;
  118. for (int cur = 0; cur < k; ++cur){
  119. if (dt[cur][u] < INF && d[cur][v] < INF)
  120. mini = min(mini, dt[cur][u] + d[cur][v]);
  121. }
  122. if (mini < INF){
  123. ++cnt;
  124. ans += mini;
  125. }
  126. }
  127. }
  128. }
  129. cout << cnt << '\n' << ans;
  130. return 0;
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement