Advertisement
Guest User

Untitled

a guest
Mar 30th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ld long double
  4. #define ll long long
  5. #define ull unsigned ll
  6.  
  7. #define f first
  8. #define s second
  9. #define pii pair < int, int >
  10.  
  11. #define pb push_back
  12. #define mp make_pair
  13.  
  14. using namespace std;
  15.  
  16. const int MXN = 1e5 + 7;
  17. const int MAXN = 1e2 + 1;
  18. const ll INF = 1e16 + 1;
  19. const int MOD = 1e9 + 7;
  20. const double EPS = 1e-9;
  21.  
  22. ll n, m;
  23. ll s, f;
  24. ll x[MXN], y[MXN], val[MXN];
  25. ll dp[MXN];
  26. ll dp1[MXN];
  27. vector < pii > g[MXN];
  28. vector < pii > g1[MXN];
  29. set < pair<long long, long long> > q;
  30. set < pair<long long, long long> > q1;
  31. int A, B;
  32.  
  33. void Dijkstra(int s, int f)
  34. {
  35.     int v;
  36.     for(int i = 1; i <= n; i++)
  37.     {
  38.         dp[i] = INF;
  39.     }
  40.     dp[s] = 0;
  41.     q.insert(mp(dp[s], s));
  42.     while(!q.empty())
  43.     {
  44.         v = q.begin() -> second;
  45.         q.erase(q.begin());
  46.         for(int i = 0; i < g[v].size(); i++)
  47.         {
  48.             int to = g[v][i].f, len = g[v][i].s;
  49.             if(dp[v] + len < dp[to])
  50.             {
  51.                 q.erase(mp(dp[to], to));
  52.                 dp[to] = dp[v] + len;
  53.                 q.insert(mp(dp[to], to));
  54.             }
  55.         }
  56.     }
  57.     return;
  58. }
  59.  
  60. long long Dijkstra1(int s, int f)
  61. {
  62.     int v;
  63.     for(int i = 1; i <= n; i++)
  64.     {
  65.         dp1[i] = INF;
  66.     }
  67.     dp1[s] = 0;
  68.     q1.insert(mp(dp1[s], s));
  69.     while(!q1.empty())
  70.     {
  71.         v = q1.begin() -> second;
  72.         q1.erase(q1.begin());
  73.         for(int i = 0; i < g1[v].size(); i++)
  74.         {
  75.             int to = g1[v][i].f, len = g1[v][i].s;
  76.             if(dp1[v] + len < dp1[to])
  77.             {
  78.                 q1.erase(mp(dp1[to], to));
  79.                 dp1[to] = dp1[v] + len;
  80.                 q1.insert(mp(dp1[to], to));
  81.             }
  82.         }
  83.     }
  84.     return dp1[f] == INF ? -1 : dp1[f];
  85. }
  86.  
  87.  
  88. int main()
  89. {
  90.     cin >> n >> m >> s >> f;
  91.     for(int i = 1; i <= m; i++)
  92.     {
  93.         cin >> x[i] >> y[i] >> val[i];
  94.     }
  95.     cin >> A >> B;
  96.     for (int i =1; i  <= n; i++) {
  97.         if (val[i] >= B) {
  98.             g1[x[i]].pb(mp(y[i], val[i]));
  99.             g1[y[i]].pb(mp(x[i], val[i]));
  100.         } if (val[i] <= A) {
  101.             g[x[i]].pb(mp(y[i], val[i]));
  102.             g[y[i]].pb(mp(x[i], val[i]));
  103.         }
  104.     }
  105.     Dijkstra(s, f);
  106.     for (int i = 1; i <= n; i++) {
  107.         if (dp[i] == INF) {
  108.             g[s].pb(mp(i, dp[i]));
  109.             g[i].pb(mp(s, dp[i]));
  110.         }
  111.     }
  112.     cout << Dijkstra1(s, f);
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement