Advertisement
Guest User

Untitled

a guest
Mar 28th, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.19 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <set>
  5. using namespace std;
  6.  
  7. #define ll long long
  8. #define mp make_pair
  9. #define pb push_back
  10.  
  11. const int LEN = 100009;
  12. const ll INF = 200000000000000000;
  13.  
  14. int n, m;
  15. int s, t;
  16. int A, B;
  17.  
  18. vector <pair<int, ll> > g[LEN];
  19. ll d[LEN][2];
  20.  
  21. int main() {
  22. scanf("%d%d%d%d", &n, &m, &s, &t);
  23. s--;
  24. t--;
  25.  
  26. int a, b, c;
  27. for (int i = 0; i < m; i++) {
  28. scanf("%d%d%d", &a, &b, &c);
  29.  
  30. g[a - 1].pb(mp(b - 1, c));
  31. g[b - 1].pb(mp(a - 1, c));
  32. }
  33.  
  34. scanf("%d%d", &A, &B);
  35.  
  36. for (int i = 0; i < n; i++) {
  37. d[i][0] = INF;
  38. d[i][1] = INF;
  39. }
  40.  
  41. d[s][0] = 0;
  42. d[s][1] = 0;
  43.  
  44. set <pair<ll, int> > heap;
  45. for (int i = 0; i < n; i++) {
  46. heap.insert(mp(d[i][0], i));
  47. }
  48. for (int q = 0; q < n; q++) {
  49. int v = (*(heap.begin())).second;
  50. heap.erase(heap.begin());
  51.  
  52. for (int i = 0; i < g[v].size(); i++) {
  53. if (g[v][i].second > A)
  54. continue;
  55.  
  56. if (d[g[v][i].first][0] > d[v][0] + g[v][i].second) {
  57. heap.erase(mp(d[g[v][i].first][0], g[v][i].first));
  58. d[g[v][i].first][0] = min(d[g[v][i].first][0], d[v][0] + g[v][i].second);
  59. heap.insert(mp(d[g[v][i].first][0], g[v][i].first));
  60. }
  61. }
  62. }
  63.  
  64. heap.clear();
  65.  
  66. for (int i = 0; i < n; i++)
  67. heap.insert(mp(d[i][1], i));
  68. for (int q = 0; q < n; q++) {
  69. int v = (*(heap.begin())).second;
  70. heap.erase(heap.begin());
  71.  
  72. for (int i = 0; i < g[v].size(); i++) {
  73. if (g[v][i].second < B)
  74. continue;
  75.  
  76. if (d[g[v][i].first][1] > min(d[v][0] + g[v][i].second, d[v][1] + g[v][i].second)) {
  77. heap.erase(mp(d[g[v][i].first][1], g[v][i].first));
  78. 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));
  79. heap.insert(mp(d[g[v][i].first][1], g[v][i].first));
  80. }
  81. }
  82. }
  83.  
  84. if (d[t][0] == INF && d[t][1] == INF)
  85. printf("-1");
  86. else
  87. printf("%lld", min(d[t][0], d[t][1]));
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement