Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF = 1000000000;
- const int N = 2 * 100000;
- #define make make_pair
- #define x first
- #define y second
- vector < pair <int, int> > a[N];
- priority_queue < pair <int, int> > q;
- int d[N];
- int main()
- {
- int n, m, s, t, A, B;
- cin >> n >> m;
- cin >> s >> t;
- s--;
- t--;
- for (int i = 0; i < m; i++)
- {
- int x, y, z;
- cin >> x >> y >> z;
- x--;
- y--;
- a[x].push_back(make(y, z));
- a[y].push_back(make(x, z));
- }
- cin >> A >> B;
- for (int i = 0; i <= n; i++)
- d[i] = INF;
- d[s] = 0;
- q.push(make(0, s));
- while (!q.empty())
- {
- int v = q.top().y;
- int cur = -q.top().x;
- q.pop();
- if (cur > d[v])
- continue;
- for (int j = 0; j < (int)a[v].size(); j++)
- {
- int to = a[v][j].x;
- int len = a[v][j].y;
- if (d[v] + len < d[to] && len <= A)
- {
- d[to] = d[v] + len;
- q.push(make(-d[to], d[to]));
- }
- }
- }
- for (int i = 0; i < n; i++)
- if (d[i] != INF)
- q.push(make(d[i], i));
- while (!q.empty())
- {
- int v = q.top().y;
- int cur = -q.top().x;
- q.pop();
- if (cur > d[v])
- continue;
- for (int j = 0; j < (int)a[v].size(); j++)
- {
- int to = a[v][j].x;
- int len = a[v][j].y;
- if (d[v] + len < d[to] && len >= B)
- {
- d[to] = d[v] + len;
- q.push(make(-d[to], d[to]));
- }
- }
- }
- if (d[t] != INF)
- cout << d[t] << endl;
- else
- cout << -1 << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement