Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ld long double
- #define ll long long
- #define ull unsigned ll
- #define f first
- #define s second
- #define pii pair < int, int >
- #define pb push_back
- #define mp make_pair
- using namespace std;
- const int MXN = 1e5 + 7;
- const int MAXN = 1e2 + 1;
- const ll INF = 1e16 + 1;
- const int MOD = 1e9 + 7;
- const double EPS = 1e-9;
- ll n, m;
- ll s, f;
- ll x[MXN], y[MXN], val[MXN];
- ll dp[MXN];
- ll dp1[MXN];
- vector < pii > g[MXN];
- vector < pii > g1[MXN];
- set < pair<long long, long long> > q;
- set < pair<long long, long long> > q1;
- int A, B;
- void Dijkstra(int s, int f)
- {
- int v;
- for(int i = 1; i <= n; i++)
- {
- dp[i] = INF;
- }
- dp[s] = 0;
- q.insert(mp(dp[s], s));
- while(!q.empty())
- {
- v = q.begin() -> second;
- q.erase(q.begin());
- for(int i = 0; i < g[v].size(); i++)
- {
- int to = g[v][i].f, len = g[v][i].s;
- if(dp[v] + len < dp[to])
- {
- q.erase(mp(dp[to], to));
- dp[to] = dp[v] + len;
- q.insert(mp(dp[to], to));
- }
- }
- }
- return;
- }
- long long Dijkstra1(int s, int f)
- {
- int v;
- for(int i = 1; i <= n; i++)
- {
- dp1[i] = INF;
- }
- dp1[s] = 0;
- q1.insert(mp(dp1[s], s));
- while(!q1.empty())
- {
- v = q1.begin() -> second;
- q1.erase(q1.begin());
- for(int i = 0; i < g1[v].size(); i++)
- {
- int to = g1[v][i].f, len = g1[v][i].s;
- if(dp1[v] + len < dp1[to])
- {
- q1.erase(mp(dp1[to], to));
- dp1[to] = dp1[v] + len;
- q1.insert(mp(dp1[to], to));
- }
- }
- }
- return dp1[f] == INF ? -1 : dp1[f];
- }
- int main()
- {
- cin >> n >> m >> s >> f;
- for(int i = 1; i <= m; i++)
- {
- cin >> x[i] >> y[i] >> val[i];
- }
- cin >> A >> B;
- for (int i =1; i <= n; i++) {
- if (val[i] >= B) {
- g1[x[i]].pb(mp(y[i], val[i]));
- g1[y[i]].pb(mp(x[i], val[i]));
- } if (val[i] <= A) {
- g[x[i]].pb(mp(y[i], val[i]));
- g[y[i]].pb(mp(x[i], val[i]));
- }
- }
- Dijkstra(s, f);
- for (int i = 1; i <= n; i++) {
- if (dp[i] == INF) {
- g[s].pb(mp(i, dp[i]));
- g[i].pb(mp(s, dp[i]));
- }
- }
- cout << Dijkstra1(s, f);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement