Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 1000000000;
  6. const int N = 2 * 100000;
  7.  
  8. #define make make_pair
  9. #define x first
  10. #define y second
  11.  
  12. vector < pair <int, int> > a[N];
  13. priority_queue < pair <int, int> > q;
  14. int d[N];
  15.  
  16. int main()
  17. {
  18. int n, m, s, t, A, B;
  19. cin >> n >> m;
  20.  
  21. cin >> s >> t;
  22. s--;
  23. t--;
  24.  
  25. for (int i = 0; i < m; i++)
  26. {
  27. int x, y, z;
  28. cin >> x >> y >> z;
  29. x--;
  30. y--;
  31.  
  32. a[x].push_back(make(y, z));
  33. a[y].push_back(make(x, z));
  34. }
  35.  
  36. cin >> A >> B;
  37.  
  38. for (int i = 0; i <= n; i++)
  39. d[i] = INF;
  40. d[s] = 0;
  41.  
  42. q.push(make(0, s));
  43.  
  44. while (!q.empty())
  45. {
  46. int v = q.top().y;
  47. int cur = -q.top().x;
  48. q.pop();
  49.  
  50. if (cur > d[v])
  51. continue;
  52.  
  53. for (int j = 0; j < (int)a[v].size(); j++)
  54. {
  55. int to = a[v][j].x;
  56. int len = a[v][j].y;
  57.  
  58. if (d[v] + len < d[to] && len <= A)
  59. {
  60. d[to] = d[v] + len;
  61. q.push(make(-d[to], d[to]));
  62. }
  63. }
  64. }
  65.  
  66. for (int i = 0; i < n; i++)
  67. if (d[i] != INF)
  68. q.push(make(d[i], i));
  69.  
  70. while (!q.empty())
  71. {
  72. int v = q.top().y;
  73. int cur = -q.top().x;
  74. q.pop();
  75.  
  76. if (cur > d[v])
  77. continue;
  78.  
  79. for (int j = 0; j < (int)a[v].size(); j++)
  80. {
  81. int to = a[v][j].x;
  82. int len = a[v][j].y;
  83.  
  84. if (d[v] + len < d[to] && len >= B)
  85. {
  86. d[to] = d[v] + len;
  87. q.push(make(-d[to], d[to]));
  88. }
  89. }
  90. }
  91.  
  92. if (d[t] != INF)
  93. cout << d[t] << endl;
  94. else
  95. cout << -1 << endl;
  96. return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement