Advertisement
GerONSo

Untitled

Jan 11th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.28 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 = 10000 + 10;
  46. const int MAXL = 510;
  47. const int INF = 1e9 + 7;
  48. const int BASE = 47;
  49. const int MOD = 1e9 + 7;
  50. const int MAXLOG = 51;
  51. const ld EPS = 1e-6;
  52.  
  53. struct pt {
  54. int u, left, cnt;
  55. };
  56.  
  57. int k, n, m, s, f;
  58. vector<vector<pair<int, int>>> g, g2;
  59. vector<bool> used(MAXN);
  60.  
  61. signed main() {
  62. seriy();
  63. cin >> k >> n >> m >> s >> f;
  64. s--;
  65. f--;
  66. g.resize(n);
  67. for(int i = 0; i < m; i++) {
  68. int u, v, w;
  69. cin >> u >> v >> w;
  70. u--;
  71. v--;
  72. g[u].push_back({v, w});
  73. g[v].push_back({u, w});
  74. }
  75. vector<bool> is(n);
  76. int l;
  77. cin >> l;
  78. int p[l];
  79. for(int i = 0; i < l; i++) {
  80. cin >> p[i];
  81. p[i]--;
  82. is[p[i]] = 1;
  83. }
  84. deque<pt> q;
  85. q.push_back({s, k, 0});
  86. vector<int> was(n, INF);
  87. int res = INF;
  88. while(q.size()) {
  89. pt u = q.front();
  90. q.pop_front();
  91. was[u.u] = min(was[u.u], u.cnt);
  92. if(u.u == f) {
  93. res = min(res, u.cnt);
  94. }
  95. for(auto v : g[u.u]) {
  96. if(u.left >= v.y && was[v.x] >= was[u.u]) {
  97. q.push_front({v.x, u.left - v.y, u.cnt});
  98. if(is[v.x]) {
  99. q.push_back({v.x, k, u.cnt + 1});
  100. }
  101. }
  102. }
  103. }
  104. cout << ((res == INF) ? -1 : res);
  105. return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement