Advertisement
OIQ

c

OIQ
Jan 14th, 2020
274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <string.h>
  5. #include <deque>
  6. using namespace std;
  7.  
  8. vector<pair<int, int>> g[10000];
  9. int path[10000][501];
  10. char tr[10000];
  11.  
  12. struct vert {
  13.     int value;
  14.     int ver;
  15.     int cruel;
  16.     vert(int a, int b, int c) :value(a), ver(b), cruel(c) {}
  17.     const bool operator < (const vert& x) const {
  18.         return value < x.value;
  19.     }
  20. };
  21.  
  22.  
  23. int main() {
  24.     // yur code goes here
  25.     int k, n, m, s, f;
  26.     cin >> k >> n >> m >> s >> f;
  27.     s--;
  28.     f--;
  29.     for (int i = 0; i < m; i++) {
  30.         int u, v, l;
  31.        
  32.         cin >> u >> v >> l;
  33.         u--;
  34.         v--;
  35.         if (l <= k) {
  36.             g[u].push_back(make_pair(v, l));
  37.             g[v].push_back(make_pair(u, l));
  38.         }
  39.     }
  40.     int q;
  41.     cin >> q;
  42.     for (int i = 0; i < q; i++) {
  43.         int a;
  44.         cin >> a;
  45.         tr[a - 1] = 1;
  46.     }
  47.     memset(path, 0x7F, sizeof(path));
  48.     path[s][k] = 0;
  49.     deque<vert> deq;
  50.     deq.push_front(vert(0, s, k));
  51.     while (!deq.empty()) {
  52.         vert cur = deq.front();
  53.         deq.pop_front();
  54.         for (auto z : g[cur.ver]) {
  55.             if (z.second <= cur.cruel)
  56.                 if (path[z.first][cur.cruel - z.second] > cur.value) {
  57.                     path[z.first][cur.cruel - z.second] = cur.value;
  58.                    
  59.                     deq.push_front(vert(cur.value, z.first, cur.cruel - z.second));
  60.                 }
  61.             if (tr[cur.ver])
  62.                 if (path[z.first][k - z.second] > cur.value + 1) {
  63.                     path[z.first][k - z.second] = cur.value + 1;
  64.  
  65.                     deq.push_back(vert(cur.value + 1, z.first, k - z.second));
  66.                 }
  67.         }
  68.     }
  69.     int res = 1e9;
  70.     for (int i = 0; i <= k; i++)
  71.         res = min(res, path[f][i]);
  72.     if (res == 1e9)
  73.         res = -1;
  74.     cout << res;
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement