Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ∧_∧
- ( ・ω・。)つ━☆・*。
- ⊂ ノ ・゜
- しーJ Accepted
- */
- // #pragma GCC optimize("O3")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define all(x) begin(x), end(x)
- #define x first
- #define y second
- // #define int long long
- using namespace std;
- using namespace __gnu_pbds;
- typedef long double ld;
- template<typename T>
- using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const ld PI = atan2(0, -1);
- void seriy() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed << setprecision(14);
- #ifdef _offline
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- const int MAXN = 10000 + 10;
- const int MAXL = 510;
- const int INF = 1e9 + 7;
- const int BASE = 47;
- const int MOD = 1e9 + 7;
- const int MAXLOG = 51;
- const ld EPS = 1e-6;
- struct pt {
- int u, left, cnt;
- };
- int k, n, m, s, f;
- vector<vector<pair<int, int>>> g, g2;
- vector<bool> used(MAXN);
- signed main() {
- seriy();
- cin >> k >> n >> m >> s >> f;
- s--;
- f--;
- g.resize(n);
- for(int i = 0; i < m; i++) {
- int u, v, w;
- cin >> u >> v >> w;
- u--;
- v--;
- g[u].push_back({v, w});
- g[v].push_back({u, w});
- }
- vector<bool> is(n);
- int l;
- cin >> l;
- int p[l];
- for(int i = 0; i < l; i++) {
- cin >> p[i];
- p[i]--;
- is[p[i]] = 1;
- }
- deque<pt> q;
- q.push_back({s, k, 0});
- vector<int> was(n, INF);
- int res = INF;
- while(q.size()) {
- pt u = q.front();
- q.pop_front();
- was[u.u] = min(was[u.u], u.cnt);
- if(u.u == f) {
- res = min(res, u.cnt);
- }
- for(auto v : g[u.u]) {
- if(u.left >= v.y && was[v.x] >= was[u.u]) {
- q.push_front({v.x, u.left - v.y, u.cnt});
- if(is[v.x]) {
- q.push_back({v.x, k, u.cnt + 1});
- }
- }
- }
- }
- cout << ((res == INF) ? -1 : res);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement