SHARE
TWEET

Untitled

a guest Oct 15th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top