Advertisement
GerONSo

Untitled

Oct 16th, 2019
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.19 KB | None | 0 0
  1. /*
  2.  
  3. ∧_∧
  4. ( ・ω・。)つ━☆・*。
  5. ⊂  ノ    ・゜
  6. しーJ   Accepted
  7.  
  8. */
  9.  
  10.  
  11.  
  12. // #pragma GCC optimize("O3")
  13. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  14.  
  15. #include <bits/stdc++.h>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18.  
  19. #define ll long long
  20. #define all(x) begin(x), end(x)
  21. #define x first
  22. #define y second
  23. #define int long long
  24.  
  25. using namespace std;
  26. using namespace __gnu_pbds;
  27.  
  28. typedef long double ld;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. cout << fixed << setprecision(14);
  39. #ifdef _offline
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 1e6 + 10;
  46. const int MAXM = 600;
  47. const int INF = 1e18;
  48. const int BASE = 47;
  49. const int MOD = 1e9 + 7;
  50. const int MAXLOG = 21;
  51.  
  52. vector<vector<pair<int, int>>> g;
  53. vector<vector<int>> g2;
  54. vector<int> gas, isgas;
  55.  
  56. void dijkstra(int a, vector<int> &d) {
  57. fill(all(d), INF);
  58. d[a] = 0;
  59. set<pair<int, int>> st;
  60. st.insert({0, a});
  61. while(st.size()) {
  62. int u = st.begin()->y;
  63. st.erase(st.begin());
  64. for(auto v : g[u]) {
  65. if(d[u] + v.y < d[v.x]) {
  66. st.erase({d[v.x], v.x});
  67. d[v.x] = d[u] + v.y;
  68. st.insert({d[v.x], v.x});
  69. }
  70. }
  71. }
  72. }
  73.  
  74. signed main() {
  75. seriy();
  76. int k, n, m, st, en;
  77. cin >> k >> n >> m >> st >> en;
  78. st--;
  79. en--;
  80. g.resize(n);
  81. g2.resize(n);
  82. isgas.resize(n);
  83. for(int i = 0; i < m; i++) {
  84. int u, v, w;
  85. cin >> u >> v >> w;
  86. u--;
  87. v--;
  88. g[u].push_back({v, w});
  89. g[v].push_back({u, w});
  90. }
  91. int l;
  92. cin >> l;
  93. gas.resize(l);
  94. for(int i = 0; i < l; i++) {
  95. cin >> gas[i];
  96. gas[i]--;
  97. isgas[gas[i]] = 1;
  98. }
  99. isgas[st] = 1;
  100. isgas[en] = 1;
  101. gas.push_back(st);
  102. gas.push_back(en);
  103. vector<vector<int>> kek(n, vector<int>(n, INF));
  104. for(int i = 0; i < n; i++) {
  105. if(isgas[i]) {
  106. dijkstra(i, kek[i]);
  107. }
  108. }
  109. for(int i = 0; i < n; i++) {
  110. for(int j = 0; j < n; j++) {
  111. if(i == j) {
  112. continue;
  113. }
  114. // cerr << kek[i][j] << " ";
  115. if(kek[i][j] <= k && isgas[j] && isgas[i]) {
  116. cerr << i << " " << j << '\n';
  117. g2[i].push_back(j);
  118. }
  119. }
  120. cerr << '\n';
  121. }
  122. queue<pair<int, int>> q;
  123. q.push({st, 0});
  124. vector<bool> used(n);
  125. used[st] = 1;
  126. while(q.size()) {
  127. pair<int, int> u = q.front();
  128. q.pop();
  129. if(u.x == en) {
  130. cerr << u.y - 1 << '\n';
  131. return cout << u.y - 1, 0;
  132. }
  133. for(auto v : g2[u.x]) {
  134. if(!used[v]) {
  135. used[v] = 1;
  136. q.push({v, u.y + 1});
  137. }
  138. }
  139. }
  140. cout << -1;
  141. return 0;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement