Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- const long long INF = 1000000000000;
- int main()
- {
- int n, m, s, f, a, b;
- cin >> n >> m;
- vector< vector < pair <int, int> > > g(n + 5);
- cin >> s >> f;
- for (int i = 0; i < m; i++)
- {
- int x, y, d;
- cin >> x >> y >> d;
- g[x - 1].push_back(make_pair(y - 1, d));
- g[y - 1].push_back(make_pair(x - 1, d));
- }
- cin >> a >> b;
- queue<int> q;
- q.push(s - 1);
- vector<long long> d(n);
- for (int i = 0; i < n; i++)
- d[i] = INF;
- d[s - 1] = 0;
- while (!q.empty())
- {
- int v = q.front();
- q.pop();
- for (size_t i = 0; i < g[v].size(); ++i)
- {
- int to = g[v][i].first;
- if ((d[v] + g[v][i].second < d[to]) && g[v][i].second >= b)
- {
- q.push(to);
- d[to] = d[v] + g[v][i].second;
- }
- }
- }
- vector<long long> d1(n);
- for (int i = 0; i < n; i++)
- d1[i] = INF;
- d1[s - 1] = 0;
- q.push(s - 1);
- while (!q.empty())
- {
- int v = q.front();
- q.pop();
- for (size_t i = 0; i < g[v].size(); ++i)
- {
- int to = g[v][i].first;
- if ( (d1[v] + g[v][i].second < d1[to]) && g[v][i].second <= a)
- {
- q.push(to);
- d1[to] = d1[v] + g[v][i].second;
- }
- }
- }
- if (d[f - 1] == INF && d1[f - 1] == INF)
- cout << -1;
- else if (d[f - 1] < d1[f - 1])
- cout << d[f - 1];
- else
- cout << d1[f - 1];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement