Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.85 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define pb push_back
  3.  
  4. #include <iostream>
  5. #include <climits>
  6. #include <algorithm>
  7. #include <iomanip>
  8. #include <cmath>
  9. #include <vector>
  10. #include <map>
  11. #include <string>
  12. #include <stack>
  13. #include <set>
  14. #include <cstdio>
  15. #include <cctype>
  16. #include <queue>
  17. #include <bitset>
  18. #include <functional>
  19. #include <cassert>
  20. #include <unordered_map>
  21.  
  22. using namespace std;
  23.  
  24. #define int long long
  25.  
  26. typedef long long ll;
  27. typedef unsigned long long ull;
  28. typedef pair<ll, ll> pll;
  29. typedef pair<int, int> pii;
  30. typedef long double ld;
  31. typedef double db;
  32.  
  33. const ll N = 1e4 + 10;
  34. const ll INF = LLONG_MAX;
  35. /*
  36. struct node {
  37. node *l, *r;
  38. int x, y;
  39. int sum;
  40. int val;
  41. node(int s) {
  42. l = nullptr;
  43. r = nullptr;
  44. y = rand();
  45. sum = s * s;
  46. val = s;
  47. x = 1;
  48. }
  49. };
  50.  
  51. int getx(node* v) {
  52. if (v == nullptr) return 0;
  53. return v->x;
  54. }
  55.  
  56. int getsum(node* v) {
  57. if (v == nullptr) return 0;
  58. return v->sum;
  59. }
  60.  
  61. void upd(node* v) {
  62. if (v == nullptr) return;
  63. v->sum = getsum(v->l) + getsum(v->r);
  64. }
  65.  
  66. pair<node*, node*> split(node*& root, int key) {
  67. if (root == nullptr) {
  68. return { nullptr, nullptr };
  69. }
  70. if (getx(root->l) <= key) {
  71. auto splitted = split(root->r, key - getx(root->l) - 1);
  72. root->r = splitted.first;
  73. upd(root);
  74. return { root, splitted.second };
  75. }
  76. else {
  77. auto splitted = split(root->l, key);
  78. root->l = splitted.second;
  79. upd(root);
  80. return { splitted.first, root };
  81. }
  82. }
  83.  
  84. node* merge(node* left, node* right) {
  85. if (left == nullptr || right == nullptr) {
  86. return right != nullptr ? right : left;
  87. }
  88. if (left->y > right->y) {
  89. left->r = merge(left->r, right);
  90. upd(left);
  91. return left;
  92. }
  93. else {
  94. right->l = merge(left, right->l);
  95. upd(right);
  96. return right;
  97. }
  98. }
  99.  
  100. int type = 0;
  101.  
  102. void erase(node*& root, int key) {
  103.  
  104. }
  105.  
  106. void insert(node *&root, int key) {
  107.  
  108. }*/
  109.  
  110.  
  111. vector<pii> g[N];
  112. int dp[N][505];
  113. set<int> is;
  114. int k;
  115. int n, m, start, endd;
  116.  
  117. void bfs() {
  118.  
  119. priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
  120. q.push({ 0, { start, k } });
  121. dp[start][k] = 0;
  122.  
  123. while (q.size()) {
  124. int cnt = q.top().second.second; // текущее кол-во энергии
  125. int u = q.top().second.first; // текущий город
  126. int c = q.top().first; // текущее кол-во использованных заправок
  127. q.pop();
  128. if (c != dp[u][cnt]) continue;
  129. for (auto to : g[u]) {
  130. int v = to.first;
  131. int len = to.second;
  132. if (len > k) continue;
  133.  
  134. if (cnt - len < 0) {
  135. if (is.find(u) != is.end()) { // если в городе, где мы находимся, есть заправка
  136. if (c + 1 < dp[v][k - len]) {
  137. dp[v][k - len] = c + 1;
  138. q.push({ c + 1, { v, k - len } });
  139. }
  140. }
  141. }
  142. else {
  143. if (c < dp[v][cnt - len]) {
  144. dp[v][cnt - len] = c;
  145. q.push({ c, { v, cnt - len } });
  146. }
  147. if (is.find(u) != is.end()) { // если в городе, где мы находимся, есть заправка
  148. if (c + 1 < dp[v][k - len]) {
  149. dp[v][k - len] = c + 1;
  150. q.push({ c + 1 , { v, k - len } });
  151. }
  152. }
  153. }
  154. }
  155. }
  156.  
  157. }
  158.  
  159.  
  160.  
  161.  
  162.  
  163. signed main() {
  164. #ifndef ONLINE_JUDGE
  165. //freopen("input.txt", "r", stdin);
  166. //freopen("output.txt", "w", stdout);
  167. #else
  168. #endif
  169. ios_base::sync_with_stdio(0);
  170. cin.tie(0); cout.tie(0);
  171.  
  172. cin >> k;
  173. cin >> n >> m >> start >> endd;
  174. while (m--) {
  175. int a, b, val;
  176. cin >> a >> b >> val;
  177. g[a].pb({ b, val });
  178. g[b].pb({ a, val });
  179. }
  180. for (int i = 0; i < 505; ++i) {
  181. fill(dp[i], dp[i] + 505, INF);
  182. }
  183.  
  184. int l;
  185. cin >> l;
  186.  
  187. while (l--) {
  188. int x;
  189. cin >> x;
  190. is.insert(x);
  191. }
  192.  
  193. bfs();
  194.  
  195. int mn = INF;
  196. for (int i = 0; i <= k; ++i) {
  197. mn = min(dp[endd][i], mn);
  198. }
  199. if (mn == INF) {
  200. cout << -1 << endl;
  201. }
  202. else {
  203. cout << mn << endl;
  204. }
  205.  
  206. return 0;
  207. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement