Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <vector>
- #include <set>
- using namespace std;
- #define ll long long
- #define mp make_pair
- #define pb push_back
- const int LEN = 100009;
- const ll INF = 200000000000000000;
- int n, m;
- int s, t;
- int A, B;
- vector <pair<int, ll> > g[LEN];
- ll d[LEN][2];
- int main() {
- scanf("%d%d%d%d", &n, &m, &s, &t);
- s--;
- t--;
- int a, b, c;
- for (int i = 0; i < m; i++) {
- scanf("%d%d%d", &a, &b, &c);
- g[a - 1].pb(mp(b - 1, c));
- g[b - 1].pb(mp(a - 1, c));
- }
- scanf("%d%d", &A, &B);
- for (int i = 0; i < n; i++) {
- d[i][0] = INF;
- d[i][1] = INF;
- }
- d[s][0] = 0;
- d[s][1] = 0;
- set <pair<ll, int> > heap;
- for (int i = 0; i < n; i++) {
- heap.insert(mp(d[i][0], i));
- }
- for (int q = 0; q < n; q++) {
- int v = (*(heap.begin())).second;
- heap.erase(heap.begin());
- for (int i = 0; i < g[v].size(); i++) {
- if (g[v][i].second > A)
- continue;
- if (d[g[v][i].first][0] > d[v][0] + g[v][i].second) {
- heap.erase(mp(d[g[v][i].first][0], g[v][i].first));
- d[g[v][i].first][0] = min(d[g[v][i].first][0], d[v][0] + g[v][i].second);
- heap.insert(mp(d[g[v][i].first][0], g[v][i].first));
- }
- }
- }
- heap.clear();
- for (int i = 0; i < n; i++)
- heap.insert(mp(d[i][1], i));
- for (int q = 0; q < n; q++) {
- int v = (*(heap.begin())).second;
- heap.erase(heap.begin());
- for (int i = 0; i < g[v].size(); i++) {
- if (g[v][i].second < B)
- continue;
- if (d[g[v][i].first][1] > min(d[v][0] + g[v][i].second, d[v][1] + g[v][i].second)) {
- heap.erase(mp(d[g[v][i].first][1], g[v][i].first));
- d[g[v][i].first][1] = min(d[g[v][i].first][1], min(d[v][0] + g[v][i].second, d[v][1] + g[v][i].second));
- heap.insert(mp(d[g[v][i].first][1], g[v][i].first));
- }
- }
- }
- if (d[t][0] == INF && d[t][1] == INF)
- printf("-1");
- else
- printf("%lld", min(d[t][0], d[t][1]));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement