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;
- int main() {
- int n, c, x, y, m, s, t, a, b;
- cin >> n >> m >> s >> t;
- s--;
- t--;
- vector < vector < pair<int,int> > > g (n);
- for (int i = 0; i < m; i++){
- cin >> x >> y >> c;
- g[x - 1].push_back(pair <int, int> (y - 1, c));
- g[y - 1].push_back(pair <int, int> (x - 1, c));
- }
- cin >> a >> b;
- vector<int> d (n, INF), p (n);
- d[s] = 0;
- set < pair<int,int> > q;
- q.insert (make_pair (d[s], s));
- while (!q.empty()) {
- int v = q.begin()->second;
- q.erase (q.begin());
- for (size_t j=0; j<g[v].size(); ++j) {
- int to = g[v][j].first,
- len = g[v][j].second;
- if (d[v] + len < d[to] && d[v] + len <= a) {
- q.erase (make_pair (d[to], to));
- d[to] = d[v] + len;
- p[to] = v;
- q.insert (make_pair (d[to], to));
- }
- }
- }
- for (long long i = 0; i < n; i++)
- if (d[i] != INF)
- q.insert(pair <int, int> (d[i], i));
- //vector<int> d (n, INF), p (n);
- while (!q.empty()) {
- int v = q.begin()->second;
- q.erase (q.begin());
- for (size_t j=0; j<g[v].size(); ++j) {
- int to = g[v][j].first,
- len = g[v][j].second;
- if (d[v] + len < d[to] && d[v] + len >= b) {
- q.erase (make_pair (d[to], to));
- d[to] = d[v] + len;
- p[to] = v;
- q.insert (make_pair (d[to], to));
- }
- }
- }
- if (d[t] != INF)
- cout << d[t];
- else
- cout << -1;
- cout << endl;
- return 0;
- }
- /*
- 4 6
- 1 4
- 1 2 4
- 2 4 4
- 4 1 6
- 1 3 7
- 4 3 10
- 3 2 2
- 5 6
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement