Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <string.h>
- #include <deque>
- using namespace std;
- vector<pair<int, int>> g[10000];
- int path[10000][501];
- char tr[10000];
- struct vert {
- int value;
- int ver;
- int cruel;
- vert(int a, int b, int c) :value(a), ver(b), cruel(c) {}
- const bool operator < (const vert& x) const {
- return value < x.value;
- }
- };
- int main() {
- // yur code goes here
- int k, n, m, s, f;
- cin >> k >> n >> m >> s >> f;
- s--;
- f--;
- for (int i = 0; i < m; i++) {
- int u, v, l;
- cin >> u >> v >> l;
- u--;
- v--;
- if (l <= k) {
- g[u].push_back(make_pair(v, l));
- g[v].push_back(make_pair(u, l));
- }
- }
- int q;
- cin >> q;
- for (int i = 0; i < q; i++) {
- int a;
- cin >> a;
- tr[a - 1] = 1;
- }
- memset(path, 0x7F, sizeof(path));
- path[s][k] = 0;
- deque<vert> deq;
- deq.push_front(vert(0, s, k));
- while (!deq.empty()) {
- vert cur = deq.front();
- deq.pop_front();
- for (auto z : g[cur.ver]) {
- if (z.second <= cur.cruel)
- if (path[z.first][cur.cruel - z.second] > cur.value) {
- path[z.first][cur.cruel - z.second] = cur.value;
- deq.push_front(vert(cur.value, z.first, cur.cruel - z.second));
- }
- if (tr[cur.ver])
- if (path[z.first][k - z.second] > cur.value + 1) {
- path[z.first][k - z.second] = cur.value + 1;
- deq.push_back(vert(cur.value + 1, z.first, k - z.second));
- }
- }
- }
- int res = 1e9;
- for (int i = 0; i <= k; i++)
- res = min(res, path[f][i]);
- if (res == 1e9)
- res = -1;
- cout << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement